Front matter
1-24
Global Development via Local Observational Construction Steps
Michel Bidoit, Donald Sannella and Andrzej Tarlecki
25-39
Edge-Colouring Pairs of Binary Trees: Towards a Concise Proof of the Four-Colour Theorem of Planar Maps
Alan Gibbons and Paul Sant
40-58
Applications of Finite Automata
Juhani Karhumäki
59-67
Approximability of the Minimum Bisection Problem: An Algorithmic Challenge
Marek Karpinski
68-80
Low Stretch Spanning Trees
David Peleg
81-92
On Radiocoloring Hierarchically Specified Planar Graphs:
PSPACE
\mathcal{P}\mathcal{S}\mathcal{P}\mathcal{A}\mathcal{C}\mathcal{E}
-Completeness and Approximations
Maria I. Andreou, Dimitris A. Fotakis, Sotiris E. Nikoletseas, Vicky G. Papadopoulou and Paul G. Spirakis
93-103
Finite Domain Constraint Satisfaction Using Quantum Computation
Ola Angelsmark, Vilhelm Dahllöf and Peter Jonsson
104-117
Fast Algorithms with Algebraic Monge Properties
Wolfgang W. Bein, Peter Brucker, Lawrence L. Larmore and James K. Park
118-130
Packing Edges in Random Regular Graphs
Mihalis Beis, William Duckworth and Michele Zito
131-142
A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications
Extended Abstract
Beate Bollig and Philipp Woelfel
143-154
Matroid Intersections, Polymatroid Inequalities, and Related Problems
Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan
155-164
Accessibility in Automata on Scattered Linear Orderings
Olivier Carton
165-176
On Infinite Terms Having a Decidable Monadic Theory
Didier Caucal
177-187
A Chomsky-Like Hierarchy of Infinite Graphs
Didier Caucal and Teodor Knapik
188-200
Competitive Analysis of On-line Stream Merging Algorithms
Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting and Prudence W. H. Wong
201-211
Coloring
k
-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming
Amin Coja-Oghlan
212-220
On Word Equations in One Variable
Robert Dabrowski and Wojtek Plandowski
221-233
Autoreducibility of Random Sets: A Sharp Bound on the Density of Guessed Bits
Todd Ebert and Wolfgang Merkle
234-244
Two-Way Finite State Transducers with Nested Pebbles
Joost Engelfriet and Sebastian Maneth
245-256
Optimal Non-preemptive Semi-online Scheduling on Two Related Machines
Leah Epstein and Lene M. Favrholdt
257-268
More on Weighted Servers or Fifo is Better than Lru
Leah Epstein, Csanád Imreh and Rob van Stee
269-279
On Maximizing the Throughput of Multiprocessor Tasks
Aleksei V. Fishkin and Guochuan Zhang
280-291
Some Results on Random Unsatisfiable
k
-Sat Instances and Approximation Algorithms Applied to Random Structures
Andreas Goerdt and Tomasz Jurdziński
292-304
Evolutive Tandem Repeats Using Hamming Distance
Richard Groult, Martine Léonard and Laurent Mouchard
305-318
Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth
MohammadTaghi Hajiaghayi and Naomi Nishimura
319-327
Computing Partial Information out of Intractable One — The First Digit of 2n at Base 3 as an Example
Mika Hirvensalo and Juhani Karhumäki
328-340
Algorithms for Computing Small NFAs
Lucian Iliea and Sheng Yu
341-352
Space-Economical Construction of Index Structures for All Suffixes of a String
Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Hideo Bannai and Setsuo Arikawa
353-364
An Explicit Lower Bound of 5
n
−
o
(
n
) for Boolean Circuits
Kazuo Iwama and Hiroki Morizumi
365-374
Computational Complexity in the Hyperbolic Plane
Chuzo Iwamoto, Takeshi Andou, Kenichi Morita and Katsunobu Imai
375-386
On a Mereological System for Relational Software Specifications
Ryszard Janicki
387-398
An Optimal Lower Bound for Resolution with 2-Conjunctions
Jan Johannsen and N. S. Narayanaswamy
399-410
Improved Parameterized Algorithms for Planar Dominating Set
Iyad A. Kanj and Ljubomir Perković
411-422
Optimal Free Binary Decision Diagrams for Computation of EARn
Jan Kára and Daniel Král’
423-432
Unification Modulo Associativity and Idempotency Is NP-complete
Ondřej Klíma
433-445
On the Complexity of Semantic Equivalences for Pushdown Automata and BPA
Antonín Kučera and Richard Mayr
446-458
An Improved Algorithm for the Membership Problem for Extended Regular Expressions
Orna Kupferman and Sharon Zuhovitzky
459-470
Efficient Algorithms for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecular Sequence Analysis
Extended Abstract
Yaw-Ling Lin, Tao Jiang and Kun-Mao Chao
471-482
Derivation of Rational Expressions with Multiplicity
Sylvain Lombardy and Jacques Sakarovitch
483-494
Hypothesis-Founded Semantics for Datalog Programs with Negation
Yann Loyer and Nicolas Spyratos
495-505
On the Problem of Scheduling Flows on Distributed Networks
Thomas Lücking, Burkhard Monien and Manuel Rode
506-518
Unit Testing for Casl
Architectural Specifications
Patricia D. L. Machado and Donald Sannella
519-531
Symbolic Semantics and Analysis for Crypto-CCS with (Almost) Generic Inference Systems
Fabio Martinelli
532-542
The Complexity of Tree Multicolorings
Dániel Marx
543-555
On Verifying Fair Lossy Channel Systems
Benoît Masson and Ph. Schnoebelen
556-567
Parameterized Counting Problems
Catherine McCartin
568-580
On the Construction of Effective Random Sets
Wolfgang Merkle and Nenad Mihailović
581-592
On the Structure of the Simulation Order of Proof Systems
Extended Abstract
Jochen Messner
593-604
Comorphism-Based Grothendieck Logics
Till Mossakowski
605-614
Finite Test-Sets for Overlap-Free Morphisms
Extended Abstract
Gwenael Richomme and Francis Wlazinski
615-624
Characterizing Simpler Recognizable Sets of Integers
Michel Rigo
625-636
Towards a Cardinality Theorem for Finite Automata
Till Tantau
637-649
An Approximation Semantics for the Propositional Mu-Calculus
Roger Villemaire
Back matter