Invited Presentations |
Recurrence in Infinite Words (Extended Abstract) / Julien Cassaigne |
Generalized Model-Checking Problems for First-Order Logic / Martin Grohe |
Myhill-Nerode Relations on Automatic Systems and the Completeness of Kleene Algebra / Dexter Kozen |
Contributions |
2-Nested Simulation Is Not Finitely Equationally Axiomatizable / Luca Aceto ; Wan Fokkink ; Anna Ingólfsdóttir |
On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems / Shin Aida ; Rainer Schuler ; Tatsuie Tsukiji ; Osamu Watanabe |
Matching Polygonal Curves with Respect to the Fréchet Distance / Helmut Alt ; Christian Knauer ; Carola Wenk |
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata / Andris Ambainis ; Arnolds Kikusts ; M&amacron;ris Valdats |
Star-Free Open Languages and Aperiodic Loops / Martin Beaudry ; Frangois Lemieux ; Denis Thérien |
5\frac2n2-Lower Bound for the Multiplicative Complexity of n x n-Matrix Multiplication / Markus Bläser |
Evasiveness of Subgraph Containment and Related Properties / Amit Chakrabarti ; Subhash Khot ; Yaoyun Shi |
On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs / Andrea E.F. Clementi ; Pilu Crescenzi ; Paolo Penna ; Gianluca Rossi ; Paola Vocca |
On Presburger Liveness of Discrete Timed Automata / Zhe Dang ; Pierluigi San Pietro ; Richard A. Kemmerer |
Residual Finite State Automata / Fraçcois Denis ; Aurélien Lemay ; Alain Terlutte |
Deterministic Radio Broadcasting at Low Cost / Anders Dessmark ; Andrzej Pelc |
The Existential Theory of Equations with Rational Constraints in Free Groups is I'PSPACE Complete / Volker Diekert ; Claudio Gutiérrez ; Christian Hagenah |
Recursive Randomized Coloring Beats Fair Dice Random Colorings / Benjamin Doerr ; Anand Srivastav |
Randomness, Computability, and Density / Rod G. Downey ; Denis R. Hirschfeldt ; André Nies |
On Multipartition Communication Complexity (Extended Abstract) / Pavol ĎDuriš ; Juraj Hromkovič ; Stasys Jukna ; Martin Sauerhoff ; Georg Schnitger |
Scalable Sparse Topologies with Small Spectrum / Robert Elsäasser ; Rastilav Královič ; Burkhard Monien |
Optimal Preemptive Scheduling on Uniform Processors with Non-decreasing Speed Ratios / Leah Epstein |
The UPS Problem / Cristina G. Fernandes ; Till Nierhoff |
Gathering of Asynchronous Oblivious Robots with Limited Visibility / Paola Flocchini ; Giuseppe Prencipe ; Nicola Santoro ; eter Widmayer |
Generalized Langton's Ant: Dynamical Behavior and Complexity / Anahí Gajardo ; Eric Goles ; Andrés Moreira |
Optimal and Approximate Station Placement in Networks (With Applications to Multicasting and Space Efficient Traversals) / Clemente Galdi ; Christos Kaklamanis ; Manuela Montangero ; Pino Persiano |
Learning Expressions over Monoids (Extended Abstract) / Ricard Gavaldá |
Efficient Recognition of Random Unsatisfiable fc-SAT Instances by Spectral Methods / Andreas Goerdt ; Michael Krivelevich |
On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages / Massimiliano Goldwurm ; Beatrice Palano ; Massimo Santini |
Efficient Minimal Perfect Hashing in Nearly Minimal Space / Torben Hagerup ; Torsten Tholey |
Small PCPs with Low Query Complexity / Prahladh Harsha ; Madhu Sudan |
Space Efficient Algorithms for Series-Parallel Graphs / Andreas Jakoby ; Maciej Liśkiewicz ; Rudiger Reischuk |
A Toolkit for First Order Extensions of Monadic Games / David Janin ; Jerzy Marcinkowski |
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs / Klaus Jansen ; Marek Karpinski ; Andrzej Lingas ; Eike Seidel |
Refining the Hierarchy of Blind Multicounter Languages / Matthias Jantzen ; Alexy Kurganskyy |
A Simple Undecidable Problem: The Inclusion Problem for Finite Substitutions on abc / Juhani Karhumdki ; Leonid P. Lisovik |
New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata / Jarkko Kari ; Cristopher Moore |
The Complexity of Minimal Satisfiability Problems / Lefteris M. Kirousis ; Phokion G. Kolaitis |
On the Minimal Hardware Complexity of Pseudorandom Function Generators (Extended Abstract) / Matthias Krause ; Stefan Lucks |
Approximation Algorithms for Minimum Size 2-Connectivity Problems / Piotr Krysta ; V.S. Anil Kumar |
A Model Theoretic Proof of Buchi-Type Theorems and First-Order Logic for N-Free Pomsets / Dietrich Kuske |
An Ehrenfeucht-Fraisse Approach to Collapse Results for First-Order Queries over Embedded Databases / Clemens Lautemann ; Nicole Schweikardt |
A New Logical Characterization of Buuchi Automata / Giacomo Lenzi |
A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraph / Liang Zhao ; Hiroshi Nagamochi ; Toshihide Ibaraki |
The Complexity of Copy Constant Detection in Parallel Programs / Markus Müller-Olm |
Approximation Algorithms for the Bottleneck Stretch Factor Problem / Giri Narasimhan ; Michiel Smid |
Semantical Principles in the Modal Logic of Coalgebras / Dirk Pattinson |
The #a = #b Pictures Are Recognizable / Klaus Reinhardt |
A Logical Approach to Decidability of Hierarchies of Regular Star-Free Languages / Victor L. Selivanov |
Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables / Howard Straubing |
New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing / Philipp Woelfel |
Author Index |
Invited Presentations |
Recurrence in Infinite Words (Extended Abstract) / Julien Cassaigne |
Generalized Model-Checking Problems for First-Order Logic / Martin Grohe |
Myhill-Nerode Relations on Automatic Systems and the Completeness of Kleene Algebra / Dexter Kozen |
Contributions |
2-Nested Simulation Is Not Finitely Equationally Axiomatizable / Luca Aceto ; Wan Fokkink ; Anna Ingólfsdóttir |