STACS 2001: 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001. Proceedings (Lecture Notes in Computer Science)

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. The Symposium On Theoretical Aspects Of Computer Science (stacs) Is Held Annually, Alternating Between France And Germany. The Stacs Meetings Are Organized Jointly By The Special Interest Group For Theoretical Computer S- Ence Of The Gesellschaft Fu ̈r Informatik (gi) In Germany And The Maison De L’informatique Et Des Math Ematiques Discr Etes (mimd) In France. Stacs2001 Was The 18th In This Series, Held In Dresden, February 15-17, 2001. Previousstacs Symposia Took Placein Paris(1984),saarbr ̈ Ucken(1985), Orsay(1986),passau(1987),bordeaux(1988),paderborn(1989),rouen(1990), Hamburg(1991),cachan(1992),wu ̈rzburg(1993),caen(1994),mu ̈nchen(1995), Grenoble (1996), Lub ̈ Eck (1997), Paris (1998), Trier (1999), And Lille (2000). It May Be Worth Noting That In 2001 The Symposium Was Held In One Of The New States Of Reunited Germany For The R St Time. The Proceedings Of All Of These Symposia Have Been Published In The Lecture Notes In Computer Science Series Of Springer{verlag. Stacs Has Become One Of The Most Important Annual Meetings In Europe For The Theoretical Computer Science Community. It Covers A Wide Range Of Topics In The Area Of Foundations Of Computer Science: Algorithms And Data Structures, Automata And Formallanguages,computationaland Structuralcomplexity, Logic, Veri Cation, And Current Challenges. This Year, 153 Submissions Were Received, Mostly In Electronic Form, From More Than 30 Countries, With A Fair Portion From Non{european Countries. We Would Like To Thank Jochen Bern Who Designed The Electronic Submission Procedure Which Performed Marvelously And Was Of Great Help To The Program Committee. 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 Nearly Minimal 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. Afonso Ferreiro [sic], Horst Reichel (eds.) Includes Bibliographical References And Index. 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 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. This work constitutes the refereed proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17th, 2001. The papers address foundational aspects of theoretical computer science such as algorithms, data structures, and automata.