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