18. STACS 2001: Dresden, Germany

Invited Presentations

• Julien Cassaigne:
  Recurrence in Infinite Words. 1-11
  
• Martin Grohe:
  Generalized Model-Checking Problems for First-Order Logic. 12-26
  
• Dexter Kozen:
  Myhill-Nerode Relations on Automatic Systems and the Completeness of Kleene Algebra. 27-38
  

Contributions

• Luca Aceto, Wan Fokkink, Anna Ingólfsdóttir:
  2-Nested Simulation Is Not Finitely Equationally Axiomatizable. 39-50
  
• Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe:
  On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems. 51-62
  
• Helmut Alt, Christian Knauer, Carola Wenk:
  Matching Polygonal Curves with Respect to the Fréchet Distance. 63-74
  
• Andris Ambainis, Arnolds Kikusts, Maris Valdats:
  On the Class of Languages Recognizable by 1-Way Quantum Finite Automata. 75-86
  
• Martin Beaudry, François Lemieux, Denis Thérien:
  Star-Free Open Languages and Aperiodic Loops. 87-98
  
• Markus Bläser:
  A (5/2)n²-Lower Bound for the Multiplicative Complexity of n×n-Matrix Multiplication. 99-109
  
• Amit Chakrabarti, Subhash Khot, Yaoyun Shi:
  Evasiveness of Subgraph Containment and Related Properties. 110-120
  
• Andrea E. F. Clementi, Pierluigi Crescenzi, Paolo Penna, Gianluca Rossi, Paola Vocca:
  On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs. 121-131
  
• Zhe Dang, Pierluigi San Pietro, Richard A. Kemmerer:
  On Presburger Liveness of Discrete Timed Automata. 132-143
  
• François Denis, Aurélien Lemay, Alain Terlutte:
  Residual Finite State Automata. 144-157
  
• Anders Dessmark, Andrzej Pelc:
  Deterministic Radio Broadcasting at Low Cost. 158-169
  
• Volker Diekert, Claudio Gutiérrez, Christian Hagenah:
  The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete. 170-182
  
• Benjamin Doerr, Anand Srivastav:
  Recursive Randomized Coloring Beats Fair Dice Random Colorings. 183-194
  
• Rodney G. Downey, Denis R. Hirschfeldt, André Nies:
  Randomness, Computability, and Density. 195-205
  
• Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger:
  On Multipartition Communication Complexity. 206-217
  
• Robert Elsässer, Rastislav Kralovic, Burkhard Monien:
  Scalable Sparse Topologies with Small Spectrum. 218-229
  
• Leah Epstein:
  Optimal Preemptive Scheduling on Uniform Processors with Non-decreasing Speed Ratios. 230-237
  
• Cristina G. Fernandes, Till Nierhoff:
  The UPS Problem. 238-246
  
• Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Peter Widmayer:
  Gathering of Asynchronous Oblivious Robots with Limited Visibility. 247-258
  
• Anahí Gajardo, Eric Goles Ch., Andrés Moreira:
  Generalized Langton's Ant: Dynamical Behavior and Complexity. 259-270
  
• Clemente Galdi, Christos Kaklamanis, Manuela Montangero, Pino Persiano:
  Optimal and Approximate Station Placement in Networks (With Applications to Multicasting and Space Efficient Traversals). 271-282
  
• Ricard Gavaldà, Denis Thérien:
  Learning Expressions over Monoids. 283-293
  
• Andreas Goerdt, Michael Krivelevich:
  Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods. 294-304
  
• Massimiliano Goldwurm, Beatrice Palano, Massimo Santini:
  On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages. 305-316
  
• Torben Hagerup, Torsten Tholey:
  Efficient Minimal Perfect Hashing in Nearly Minimal Space. 317-326
  
• Prahladh Harsha, Madhu Sudan:
  Small PCPs with Low Query Complexity. 327-338
  
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Space Efficient Algorithms for Series-Parallel Graphs. 339-352
  
• David Janin, Jerzy Marcinkowski:
  A Toolkit for First Order Extensions of Monadic Games. 353-364
  
• Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel:
  Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. 365-375
  
• Matthias Jantzen, Alexy Kurganskyy:
  Refining the Hierarchy of Blind Multicounter Languages. 376-387
  
• Juhani Karhumäki, Leonid P. Lisovik:
  A Simple Undecidable Problem: The Inclusion Problem for Finite Substitutions on ab^*c. 388-395
  
• Jarkko Kari, Cristopher Moore:
  New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata. 396-406
  
• Lefteris M. Kirousis, Phokion G. Kolaitis:
  The Complexity of Minimal Satisfiability Problems. 407-418
  
• Matthias Krause, Stefan Lucks:
  On the Minimal Hardware Complexity of Pseudorandom Function Generators. 419-430
  
• Piotr Krysta, V. S. Anil Kumar:
  Approximation Algorithms for Minimum Size 2-Connectivity Problems. 431-442
  
• Dietrich Kuske:
  A Model Theoretic Proof of Büchi-Type Theorems and First-Order Logic for N-Free Pomsets. 443-454
  
• Clemens Lautemann, Nicole Schweikardt:
  An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases. 455-466
  
• Giacomo Lenzi:
  A New Logical Characterization of Büchi Automata. 467-477
  
• Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki:
  A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraph. 478-489
  
• Markus Müller-Olm:
  The Complexity of Copy Constant Detection in Parallel Programs. 490-501
  
• Giri Narasimhan, Michiel H. M. Smid:
  Approximation Algorithms for the Bottleneck Stretch Factor Problem. 502-513
  
• Dirk Pattinson:
  Semantical Principles in the Modal Logic of Coalgebras. 514-526
  
• Klaus Reinhardt:
  The #a = #b Pictures Are Recognizable. 527-538
  
• Victor L. Selivanov:
  A Logical Approach to Decidability of Hierarchies of Regular Star-Free Languages. 539-550
  
• Howard Straubing, Denis Thérien:
  Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables. 551-562
  
• Philipp Woelfel:
  New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing. 563-574