STACS 2001 [electronic resource] : 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001. Proceedings /

Invited Presentations -- Recurrence in Infinite Words -- Generalized Model-Checking Problems for First-Order Logic -- Myhill-Nerode Relations on Automatic Systems and the Completeness of Kleene Algebra -- Contributions -- 2-Nested Simulation Is Not Finitely Equationally Axiomatizable -- On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems -- Matching Polygonal Curves with Respect to the Fréchet Distance -- On the Class of Languages Recognizable by 1-Way Quantum Finite Automata -- Star-Free Open Languages and Aperiodic Loops -- A 5/2n 2-Lower Bound for the Multiplicative Complexity of n × n-Matrix Multiplication -- Evasiveness of Subgraph Containment and Related Properties -- On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs -- On Presburger Liveness of Discrete Timed Automata -- Residual Finite State Automata -- Deterministic Radio Broadcasting at Low Cost -- The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE—Complete -- Recursive Randomized Coloring Beats Fair Dice Random Colorings -- Randomness, Computability, and Density -- On Multipartition Communication Complexity -- Scalable Sparse Topologies with Small Spectrum -- Optimal Preemptive Scheduling on Uniform Processors with Non-decreasing Speed Ratios -- The UPS Problem -- Gathering of Asynchronous Oblivious Robots with Limited Visibility -- Generalized Langton’s Ant: Dynamical Behavior and Complexity -- Optimal and Approximate Station Placement in Networks -- Learning Expressions over Monoids -- Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods -- On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages -- Efficient Minimal Perfect Hashing in NearlyMinimal Space -- Small PCPs with Low Query Complexity -- Space Efficient Algorithms for Series-Parallel Graphs -- A Toolkit for First Order Extensions of Monadic Games -- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs -- Refining the Hierarchy of Blind Multicounter Languages -- A Simple Undecidable Problem: The Inclusion Problem for Finite Substitutions on ab*c -- New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata -- The Complexity of Minimal Satisfiability Problems -- On the Minimal Hardware Complexity of Pseudorandom Function Generators -- Approximation Algorithms for Minimum Size 2-Connectivity Problems -- A Model Theoretic Proof of Büchi-Type Theorems and First-Order Logic for N-Free Pomsets -- An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases -- A New Logical Characterization of Büchi Automata -- A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraph -- The Complexity of Copy Constant Detection in Parallel Programs -- Approximation Algorithms for the Bottleneck Stretch Factor Problem -- Semantical Principles in the Modal Logic of Coalgebras -- The #a = #b Pictures Are Recognizable -- A Logical Approach to Decidability of Hierarchies of Regular Star—Free Languages -- Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables -- New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing.