STACS 99: 16th Annual Symposium on Theoretical Aspects of Computer Science Trier, Germany, March 4–6, 1999 Proceedings

Noam Nisan (auth.), Christoph Meinel, Sophie Tison (eds.)354065691X, 9783540656913

This book constitutes the refereed proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 99, held in Trier, Germany in March 1999. The 51 revised full papers presented were selected from a total of 146 submissions. Also included are three invited papers. The volume is divided in topical sections on complexity, parallel algorithms, computational geometry, algorithms and data structures, automata and formal languages, verification, algorithmic learning, and logic in computer science.

---

Table of contents :
Algorithms for Selfish Agents….Pages 1-15
The Reduced Genus of a Multigraph….Pages 16-31
Classifying Discrete Temporal Properties….Pages 32-46
Circuit Complexity of Testing Square-Free Numbers….Pages 47-56
Relating Branching Program Size and Formula Size over the Full Binary Basis….Pages 57-67
Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines….Pages 68-77
The Average Time Complexity to Compute Prefix Functions in Processor Networks….Pages 78-89
On the Hardness of Permanent….Pages 90-99
One-Sided Versus Two-Sided Error in Probabilistic Computation….Pages 100-109
An Optimal Competitive Strategy for Walking in Streets….Pages 110-120
An Optimal Strategy for Searching in Unknown Streets….Pages 121-131
Parallel Searching on m Rays….Pages 132-142
A Logical Characterisation of Linear Time on Nondeterministic Turing Machines….Pages 143-152
Descriptive Complexity of Computable Sequences….Pages 153-162
Complexity of Some Problems in Universal Algebra….Pages 163-172
New Branchwidth Territories….Pages 173-183
Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructions….Pages 184-196
Treewidth and Minimum Fill-In of Weakly Triangulated Graphs….Pages 197-206
Decidability and Undecidability of Marked PCP….Pages 207-216
On Quadratic Word Equations….Pages 217-226
Some Undecidability Results Related to the Star Problem in Trace Monoids….Pages 227-236
An Approximation Algorithm for Max p -Section….Pages 237-247
Approximating Bandwidth by Mixing Layouts of Interval Graphs….Pages 248-258
Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs….Pages 259-269
Extending Downward Collapse from 1-versus-2 Queries to j -versus- j + 1 Queries….Pages 270-280
Sparse Sets, Approximable Sets, and Parallel Queries to NP….Pages 281-290
External Selection….Pages 291-301
Fast Computations of the Exponential Function….Pages 302-312
A Model of Behaviour Abstraction for Communicating Processes….Pages 313-322
Model Checking Lossy Vector Addition Systems….Pages 323-333
Constructing Light Spanning Trees with Small Routing Cost….Pages 334-344
Finding Paths with the Right Cost….Pages 345-355
In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved?….Pages 356-361
Lower Bounds for Dynamic Algebraic Problems….Pages 362-372
An Explicit Lower Bound for TSP with Distances One and Two….Pages 373-382
Scheduling Dynamic Graphs….Pages 383-392
Supporting Increment and Decrement Operations in Balancing Networks….Pages 393-403
Worst-Case Equilibria….Pages 404-413
A Complete and Tight Average-Case Analysis of Learning Monomials….Pages 414-423
Costs of General Purpose Learning….Pages 424-433
Universal Distributions and Time-Bounded Kolmogorov Complexity….Pages 434-443
The Descriptive Complexity Approach to LOGCFL….Pages 444-454
The Weakness of Self-Complementation….Pages 455-466
On the Difference of Horn Theories….Pages 467-477
On Quantum Algorithms for Noncommutative Hidden Subgroups….Pages 478-487
On the Size of Randomized OBDDs and Read-Once Branching Programs for k -Stable Functions….Pages 488-499
How To Forget a Secret….Pages 500-509
A Modal Fixpoint Logic with Chop….Pages 510-520
Completeness of Neighbourhood Logic….Pages 521-530
Eliminating Recursion in the μ-Calculus….Pages 531-540
On Optimal Algorithms and Optimal Proof Systems….Pages 541-550
Space Bounds for Resolution….Pages 551-560
Upper Bounds for Vertex Cover Further Improved….Pages 561-570
Online Matching for Scheduling Problems….Pages 571-580