STACS 2001: 18th Annual Symposium on Theoretical Aspects of Computer Science Dresden, Germany, February 15–17, 2001 Proceedings

Recurrence in Infinite Words....Pages 1-11
Generalized Model-Checking Problems for First-Order Logic....Pages 12-26
Myhill-Nerode Relations on Automatic Systems and the Completeness of Kleene Algebra....Pages 27-38
2-Nested Simulation Is Not Finitely Equationally Axiomatizable....Pages 39-50
On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems....Pages 51-62
Matching Polygonal Curves with Respect to the Fréchet Distance....Pages 63-74
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata....Pages 75-86
Star-Free Open Languages and Aperiodic Loops....Pages 87-98
A 5/2 n 2 -Lower Bound for the Multiplicative Complexity of n × n -Matrix Multiplication....Pages 99-109
Evasiveness of Subgraph Containment and Related Properties....Pages 110-120
On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs....Pages 121-131
On Presburger Liveness of Discrete Timed Automata....Pages 132-143
Residual Finite State Automata....Pages 144-157
Deterministic Radio Broadcasting at Low Cost....Pages 158-169
The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE—Complete....Pages 170-182
Recursive Randomized Coloring Beats Fair Dice Random Colorings....Pages 183-194
Randomness, Computability, and Density....Pages 195-205
On Multipartition Communication Complexity....Pages 206-217
Scalable Sparse Topologies with Small Spectrum....Pages 218-229
Optimal Preemptive Scheduling on Uniform Processors with Non-decreasing Speed Ratios....Pages 230-237
The UPS Problem....Pages 238-246
Gathering of Asynchronous Oblivious Robots with Limited Visibility....Pages 247-258
Generalized Langton’s Ant: Dynamical Behavior and Complexity....Pages 259-270
Optimal and Approximate Station Placement in Networks....Pages 271-282
Learning Expressions over Monoids....Pages 283-293
Efficient Recognition of Random Unsatisfiable k -SAT Instances by Spectral Methods....Pages 294-304
On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages....Pages 305-316
Efficient Minimal Perfect Hashing in Nearly Minimal Space....Pages 317-326
Small PCPs with Low Query Complexity....Pages 327-338
Space Efficient Algorithms for Series-Parallel Graphs....Pages 339-352
A Toolkit for First Order Extensions of Monadic Games....Pages 353-364
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs....Pages 365-375
Refining the Hierarchy of Blind Multicounter Languages....Pages 376-387
A Simple Undecidable Problem: The Inclusion Problem for Finite Substitutions on ab * c....Pages 388-395
New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata....Pages 396-406
The Complexity of Minimal Satisfiability Problems....Pages 407-418
On the Minimal Hardware Complexity of Pseudorandom Function Generators....Pages 419-430
Approximation Algorithms for Minimum Size 2-Connectivity Problems....Pages 431-442
A Model Theoretic Proof of Büchi-Type Theorems and First-Order Logic for N-Free Pomsets....Pages 443-454
An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases....Pages 455-466
A New Logical Characterization of Büchi Automata....Pages 467-477
A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraph....Pages 478-489
The Complexity of Copy Constant Detection in Parallel Programs....Pages 490-501
Approximation Algorithms for the Bottleneck Stretch Factor Problem....Pages 502-513
Semantical Principles in the Modal Logic of Coalgebras....Pages 514-526
The #a = #b Pictures Are Recognizable....Pages 527-538
A Logical Approach to Decidability of Hierarchies of Regular Star—Free Languages....Pages 539-550
Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables....Pages 551-562
New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing....Pages 563-574