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

Julien Cassaigne (auth.), Afonso Ferreira, Horst Reichel (eds.)3540416951, 9783540416951

This book constitutes the refereed proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001, held in Dresden, Germany in February 2001.
The 46 revised full papers presented together with three invited papers were carefully reviewed and selected from a total of 153 submissions. The papers address foundational aspects from all current areas of theoretical computer science including algorithms, data structures, automata, formal languages, complexity, verification, logic, graph theory, optimization, etc.

---

Table of contents :
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