Front matter
1-2
A New Category for Semantics
Dana S. Scott
3-17
On Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity
Peter Bürgisser
18-33
Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
Erik D. Demaine
33-36
Some Recent Results on Data Mining and Search
Amos Fiat
37-57
Hypertree Decompositions: A Survey
Georg Gottlob, Nicola Leone and Francesco Scarcello
58-61
The Strength of Non-size-increasing Computation (Introduction and Summary)
Martin Hofmann
62-74
Introduction to Recent Quantum Algorithms
Peter Høyer
74-86
Decomposition Methods and Sampling Circuits in the Cartesian Lattice
Dana Randall
87-95
New Algorithms for
k
-SAT Based on the Local Search Principle
Uwe Schöning
96-110
Linear Temporal Logic and Finite Semigroups
Thomas Wilke
111-123
Refined Search Tree Technique for Dominating Set
on Planar Graphs
Jochen Alber, Hongbing Fan, Michael R. Fellows, Henning Fernau and Rolf Niedermeier, et al.
123-134
The Computational Power of a Family of Decision Forests
Kazuyuki Amano, Tsukuru Hirosawa, Yusuke Watanabe and Akira Maruoka
135-147
Exact Results for Accepting Probabilities of Quantum Automata
Andris Ambainis and Arnolds Ķikusts
148-158
Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms
Albert Atserias
159-172
Analysis Problems for Sequential Dynamical Systems and Communicating State Machines
Chris Barrett, Harry B. Hunt, Madhav V. Marathe, S. S. Ravi and Daniel J. Rosenkrantz, et al.
173-185
The Complexity of Tensor Circuit Evaluation
Extended Abstract
Martin Beaudry and Markus Holzer
186-197
Computing Reciprocals of Bivariate Power Series
Markus Bläser
198-211
Automatic Verification of Recursive Procedures with One Integer Parameter
Ahmed Bouajjani, Peter Habermehl and Richard Mayr
212-223
Graph-Driven Free Parity BDDs: Algorithms and Lower Bounds
Henrik Brosenne, Matthias Homeister and Stephan Waack
224-235
Computable Versions of Baire’s Category Theorem
Vasco Brattka
236-247
Automata on Linear Orderings
Véronique Bruyère and Olivier Carton
248-260
Algorithmic Information Theory and Cellular Automata Dynamics
Julien Cervelle, Bruno Durand and Enrico Formenti
260-271
The
k
-Median Problem for Directed Trees
Extended Abstract
Marek Chrobak, Lawrence L. Larmore and Wojciech Rytter
272-284
On Pseudorandom Generators in NC0
Mary Cryan and Peter Bro Miltersen
285-291
There Are No Sparse NPw-Hard Sets
Felipe Cucker and Dima Grigoriev
292-304
Sharing One Secret vs. Sharing Many Secrets: Tight Bounds for the Max Improvement Ratio
Giovanni Di Crescenzo
304-315
(H,C,K)
-Coloring: Fast, Easy, and Hard Cases
Josep Díaz, Maria Serna and Dimitrios M. Thilikos
316-327
Randomness and Reductibility
Rod G. Downey, Denis R. Hirschfeldt and Geoff La Forte
328-337
On the Computational Complexity of Infinite Words
Pavol Ďuriš and Ján Maňuch
338-350
Lower Bounds for On-Line Single-Machine Scheduling
Leah Epstein and Rob van Stee
351-362
Approximation Algorithms and Complexity Results for Path Problems in Trees of Rings
Thomas Erlebach
363-374
A 3-Approximation Algorithm for Movement Minimization in Conveyor Flow Shop Processing
Wolfgang Espelage and Egon Wanke
375-386
Quantifier Rank for Parity of Embedded Finite Models
Hervé Fournier
387-397
Space Hierarchy Theorem Revised
Viliam Geffert
398-407
Converting Two—Way Nondeterministic Unary Automata into Simpler Automata
Viliam Geffert, Carlo Mereghetti and Giovanni Pighizzini
408-420
The Complexity of the Minimal Polynomial
Thanh Minh Hoang and Thomas Thierauf
421-431
Note on Minimal Finite Automata
Galina Jirásková
432-438
Synchronizing Finite Automata on Eulerian Digraphs
Jarkko Kari
439-450
A Time Hierarchy for Bounded One-Way Cellular Automata
Andreas Klein and Martin Kutrib
451-463
Checking Amalgamability Conditions forCasl
Architectural Specifications
Bartek Klin, Piotr Hoffman, Andrzej Tarlecki, Lutz Schröder and Till Mossakowski
464-473
On-Line Scheduling with Tight Deadlines
Chiu-Yuen Koo, Tak-Wah Lam, Tsuen-Wan Ngan and Kar-Keung To
474-485
Complexity Note on Mixed Hypergraphs
Daniel Král’, Jan Kratochvíl and Heinz-Jürgen Voss
487-499
News from the Online Traveling Repairman
Sven O. Krumke, Willem E. de Paepe, Diana Poensgen and Leen Stougie
500-512
Word Problems for 2-Homogeneous Monoids and Symmetric Logspace
Markus Lohrey
512-523
Variations on a Theorem of Fine & Wilf
Filippo Mignosi, Jeffrey Shallit and Ming-wei Wang
524-536
Upper Bounds on the Bisection Width of 3- and 4-Regular Graphs
Burkhard Monien and Robert Preis
537-547
Satisfiability of Systems of Equations over Finite Monoids
Cristopher Moore, Pascal Tesson and Denis Thérien
548-559
Rational Graphs Trace Context-Sensitive Languages
Christophe Morvan and Colin Stirling
560-572
Towards Regular Languages over Infinite Alphabets
Frank Neven, Thomas Schwentick and Victor Vianu
573-584
Partial Information and Special Case Algorithms
Arfst Nickelsen
585-597
The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs
Mitsunori Ogihara and Seinosuke Toda
598-610
From Bidirectionality to Alternation
Nir Piterman and Moshe Y. Vardi
611-620
Syntactic Semiring of a Language
(Extended Abstract)
Libor Polák
621-632
On Reducibility and Symmetry of Disjoint NP-Pairs
Pavel Pudlák
633-644
Hierarchy of Monotonically Computable Real Numbers
Extended Abstract
Robert Rettinger and Xizhong Zheng
645-656
On the Equational Definition of the Least Prefixed Point
Luigi Santocanale
657-665
On the Periods of Partial Words
Arseny M. Shur and Yulia V. Konovalova
666-677
The Size of Power Automata
Klaus Sutner
678-689
On the Approximability of the Steiner Tree Problem
Martin Thimm
690-703
Alignment between Two RNA Structures
Zhuozhi Wang and Kaizhong Zhang
703-714
Characterization of Context-Free Languages with Polynomially Bounded Ambiguity
Klaus Wich
Back matter