| Invited Talks |
| Global Development via Local Observational Construction Steps / Michel Bidoit ; Donald Sannella ; Andrzej Tarlecki |
| Edge-Colouring Pairs of Binary Trees: Towards a Concise Proof of the Four-Colour Theorem of Planar Maps / Alan Gibbons ; Paul Sant |
| Applications of Finite Automata / Juhani Karhumäki |
| Approximability of the Minimum Bisection Problem: An Algorithmic Challenge / Marek Karpinski |
| Low Stretch Spanning Trees / David Peleg |
| Contributed Talks |
| On Radiocoloring Hierarchically Specified Planar Graphs: <$>{\cal PSPACE}<$>-Completeness and Approximations / Maria I. Andreou ; Dimitris A. Fotakis ; Sotiris E. Nikoletseas ; Vicky G. Papadopoulou ; Paul G. Spirakis |
| Finite Domain Constraint Satisfaction Using Quantum Computation / Ola Angelsmark ; Vilhelm Dahllöf ; Peter Jonsson |
| Fast Algorithms with Algebraic Monge Properties / Wolfgang W. Bein ; Peter Brucker ; Lawrence L. Larmore ; James K. Park |
| Packing Edges in Random Regular Graphs / Mihalis Beis ; William Duckworth ; Michele Ziio |
| A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications / Beate Bollig ; Philipp Woelfel |
| Matroid Intersections, Polymatroid Inequalities, and Related Problems / Endre Boros ; Khaled Elbassioni ; Vladimir Gurvich ; Leonid Khachiyan |
| Accessibility in Automata on Scattered Linear Orderings / Olivier Carton |
| On Infinite Terms Having a Decidable Monadic Theory / Didier Caucal |
| A Chomsky-Like Hierarchy of Infinite Graphs / Teodor Knapik |
| Competitive Analysis of On-line Stream Merging Algorithms / Wun-Tat Chan ; Tak-Wah Lam ; Hing-Fung Ting ; Prudence W.H. Wong |
| Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming / Amin Coja-Oghlan |
| On Word Equations in One Variable / Robert D&acedil;browski ; Wojtek Plandowski |
| Autoreducibility of Random Sets: A Sharp Bound on the Density of Guessed Bits / Todd Ebert ; Wolfgang Merkle |
| Two-Way Finite State Transducers with Nested Pebbles / Joost Engelfriet ; Sebastian Maneth |
| Optimal Non-preemptive Semi-online Scheduling on Two Related Machines / Leah Epstein ; Lene M. Favrholdt |
| More on Weighted Servers or Fifo is Better than Lru / Csanád Imreh ; Rob van Stee |
| On Maximizing the Throughput of Multiprocessor Tasks / Aleksei V. Fishkin ; Guochuan Zhang |
| Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures / Andreas Goerdt ; Tomasz Jurdziński |
| Evolutive Tandem Repeats Using Hamming Distance / Richard Groult ; Martine Léonard ; Laurent Mouchard |
| Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth / MohammadTaghi Hajiaghayi ; Naomi Nishimura |
| Computing Partial Information out of Intractable One - The First Digit of 2n at Base 3 as an Example / Mika Hirvensalo |
| Algorithms for Computing Small NFAs / Lucian Ilie ; Sheng Yu |
| Space-Economical Construction of Index Structures for All Suffixes of a String / Shunsuke Inenaga ; Ayumi Shinohara ; Masayuki Takeda ; Hideo Bannai ; Setsuo Arikawa |
| An Explicit Lower Bound of 5n - o(n) for Boolean Circuits / Kazuo Iwama ; Hiroki Morizumi |
| Computational Complexity in the Hyperbolic Plane / Chuzo Iwamoto ; Takeshi Andou ; Kenichi Morita ; Katsunobu Imai |
| On a Mereological System for Relational Software Specifications / Ryszard Janicki |
| An Optimal Lower Bound for Resolution with 2-Conjunctions / Jan Johannsen ; N.S. Narayanaswamy |
| Improved Parameterized Algorithms for Planar Dominating Set / Iyad A. Kanj ; Ljubomir Perković |
| Optimal Free Binary Decision Diagrams for Computation of EARn / Jan Kára ; Daniel Král' |
| Unification Modulo Associativity and Idempotency Is NP-complete / Ondřej Klíma |
| On the Complexity of Semantic Equivalences for Pushdown Automata and BPA / Antonín Kučera ; Richard Mayr |
| An Improved Algorithm for the Membership Problem for Extended Regular Expressions / Orna Kupferman ; Sharon Zuhovitzky |
| Efficient Algorithms for Locating the Length-Constrained Heaviest Segments,with Applications to Biomolecular Sequence Analysis / Yaw-Ling Lin ; Tao Jiang ; Kun-Mao Chao |
| Derivation of Rational Expressions with Multiplicity / Sylvain Lombardy ; Jacques Sakarovitch |
| Hypothesis-Founded Semantics for Datalog Programs with Negation / Yann Loyer ; Nicolas Spyratos |
| On the Problem of Scheduling Flows on Distributed Networks / Thomas Lücking ; Burkhard Monien ; Manuel Rode |
| Unit Testing for CASL Architectural Specifications / Patricia D.L. Machado |
| Symbolic Semantics and Analysis for Crypto-CCS with (Almost) Generic Inference Systems / Fabio Martinelli |
| The Complexity of Tree Multicolorings / Dániel Marx |
| On Verifying Fair Lossy Channel Systems / Benoît Masson ; Ph. Schnoebelen |
| Parameterized Counting Problems / Catherine McCartin |
| On the Construction of Effective Random Sets / Nenad Mihailović |
| On the Structure of the Simulation Order of Proof Systems / Jochen Messner |
| Comorphism-Based Grothendieck Logics / Till Mossakowski |
| Finite Test-Sets for Overlap-Free Morphisms / Gwenael Richomme ; Francis Wlazinski |
| Characterizing Simpler Recognizable Sets of Integers / Michel Rigo |
| Towards a Cardinality Theorem for Finite Automata / Till Tantau |
| An Approximation Semantics for the Propositional Mu-Calculus / Roger Villemaire |
| Author Index |
| Invited Talks |
| Global Development via Local Observational Construction Steps / Michel Bidoit ; Donald Sannella ; Andrzej Tarlecki |
| Edge-Colouring Pairs of Binary Trees: Towards a Concise Proof of the Four-Colour Theorem of Planar Maps / Alan Gibbons ; Paul Sant |
| Applications of Finite Automata / Juhani Karhumäki |
| Approximability of the Minimum Bisection Problem: An Algorithmic Challenge / Marek Karpinski |
| Low Stretch Spanning Trees / David Peleg |
