STACS 2001

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.