Front matter
1-20
Distributed Quantum Computing
Harry Buhrman and Hein Röhrig
21-45
Selfish Routing in Non-cooperative Networks: A Survey
R. Feldmann, M. Gairing, Thomas Lücking, Burkhard Monien and Manuel Rode
46-67
Process Algebraic Frameworks for the Specification and Analysis of Cryptographic Protocols
Roberto Gorrieri and Fabio Martinelli
68-91
Semantic and Syntactic Approaches to Simulation Relations
Jo Hannay, Shin-ya Katsumata and Donald Sannella
92-112
On the Computational Complexity of Conservative Computing
Giancarlo Mauri and Alberto Leporati
113-124
Constructing Infinite Graphs with a Decidable MSO-Theory
Wolfgang Thomas
125-141
Towards a Theory of Randomized Search Heuristics
Ingo Wegener
142-151
Adversarial Models for Priority-Based Networks
C. Àlvarez, M. Blesa, J. Díaz, A. Fernández and M. Serna
152-161
On Optimal Merging Networks
Kazuyuki Amano and Akira Maruoka
162-168
Problems which Cannot Be Reduced to Any Proper Subproblems
Klaus Ambos-Spies
169-178
ACID-Unification Is NEXPTIME-Decidable
Siva Anantharaman, Paliath Narendran and Michael Rusinowitch
179-188
Completeness in Differential Approximation Classes
G. Ausiello, C. Bazgan, M. Demange and V. Th. Paschos
189-197
On the Length of the Minimum Solution of Word Equations in One Variable
Kensuke Baba, Satoshi Tsuruta, Ayumi Shinohara and Masayuki Takeda
198-207
Smoothed Analysis of Three Combinatorial Problems
Cyril Banderier, René Beier and Kurt Mehlhorn
208-217
Inferring Strings from Graphs and Arrays
Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara and Masayuki Takeda
218-227
Faster Algorithms for k-Medians in Trees
Robert Benkoczi, Binay Bhattacharya, Marek Chrobak, Lawrence L. Larmore and Wojciech Rytter
228-238
Periodicity and Transitivity for Cellular Automata in Besicovitch Topologies
F. Blanchard, J. Cervelle and E. Formenti
239-248
Starting with Nondeterminism: The Systematic Derivation of Linear-Time Graph Layout Algorithms
Hans L. Bodlaender, Michael R. Fellows and Dimitrios M. Thilikos
249-258
Error-Bounded Probabilistic Computations between MA and AM
Elmar Böhler, Christian Glaßer and Daniel Meister
259-268
A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves
Paul S. Bonsma, Tobias Brueggemann and Gerhard J. Woeginger
269-278
Symbolic Analysis of Crypto-Protocols Based on Modular Exponentiation
Michele Boreale and Maria Grazia Buscemi
279-289
Denotational Testing Semantics in Coinductive Form
Michele Boreale and Fabio Gadducci
290-299
Lower Bounds for General Graph–Driven Read–Once Parity Branching Programs
Henrik Brosenne, Matthias Homeister and Stephan Waack
300-307
The Minimal Graph Model of Lambda Calculus
Antonio Bucciarelli and Antonino Salibra
308-317
Unambiguous Automata on Bi-infinite Words
Olivier Carton
318-327
Relating Hierarchy of Temporal Properties to Model Checking
Ivana Černá and Radek Pelánek
328-337
Arithmetic Constant-Depth Circuit Complexity Classes
Hubie Chen
338-347
Inverse NP Problems
Hubie Chen
348-357
A Linear-Time Algorithm for 7-Coloring 1-Planar Graphs
Zhi-Zhong Chen and Mitsuharu Kouno
358-367
Generalized Satisfiability with Limited Occurrences per Variable: A Study through Delta-Matroid Parity
Victor Dalmau and Daniel K. Ford
368-377
Randomized Algorithms for Determining the Majority on Graphs
Gianluca De Marco and Andrzej Pelc
378-387
Using Transitive–Closure Logic for Deciding Linear Properties of Monoids
Christian Delhommé, Teodor Knapik and D. Gnanaraj Thomas
388-397
Linear-Time Computation of Local Periods
Jean-Pierre Duval, Roman Kolpakov, Gregory Kucherov, Thierry Lecroq and Arnaud Lefebvre
398-407
Two Dimensional Packing: The Power of Rotation
Leah Epstein
408-418
Approximation Schemes for the Min-Max Starting Time Problem
Leah Epstein and Tamir Tassa
419-428
Quantum Testers for Hidden Group Properties
Katalin Friedl, Frédéric Magniez, Miklos Santha and Pranab Sen
429-438
Local LTL with Past Constants Is Expressively Complete for Mazurkiewicz Traces
Paul Gastin, Madhavan Mukund and K. Narayan Kumar
439-448
LTL with Past and Two-Way Very-Weak Alternating Automata
Paul Gastin and Denis Oddoux
449-459
Match-Bounded String Rewriting Systems
Alfons Geser, Dieter Hofbauer and Johannes Waldmann
460-469
Probabilistic and Nondeterministic Unary Automata
Gregor Gramlich
470-479
On Matroid Properties Definable in the MSO Logic
Petr Hliněný
480-489
Characterizations of Catalytic Membrane Computing Systems
Oscar H. Ibarra, Zhe Dang, Omer Egecioglu and Gaurav Saxena
490-499
Augmenting Local Edge-Connectivity between Vertices and Vertex Subsets in Undirected Graphs
Toshimasa Ishii and Masayuki Hagiwara
500-510
Scheduling and Traffic Allocation for Tasks with Bounded Splittability
Piotr Krysta, Peter Sanders and Berthold Vöcking
511-520
Computing Average Value in Ad Hoc Networks
Mirosław Kutyłowski and Daniel Letkiewicz
521-530
A Polynomial-Time Algorithm for Deciding True Concurrency Equivalences of Basic Parallel Processes
Sławomir Lasota
531-540
Solving the Sabotage Game Is PSPACE-Hard
Christof Löding and Philipp Rohde
541-550
The Approximate Well-Founded Semantics for Logic Programs with Uncertainty
Yann Loyer and Umberto Straccia
551-561
Which Is the Worst-Case Nash Equilibrium?
Thomas Lücking, Marios Mavronicolas, Burkhard Monien, Manuel Rode and Paul Spirakis, et al.
562-571
A Unique Decomposition Theorem for Ordered Monoids with Applications in Process Theory
Bas Luttik
572-581
Generic Algorithms for the Generation of Combinatorial Objects
Conrado Martínez and Xavier Molinero
582-591
On the Complexity of Some Problems in Interval Arithmetic
K. Meer
592-601
An Abduction-Based Method for Index Relaxation in Taxonomy-Based Sources
Carlo Meghini, Yannis Tzitzikas and Nicolas Spyratos
602-611
On Selection Functions that Do Not Preserve Normality
Wolfgang Merkle and Jan Reimann
612-621
On Converting CNF to DNF
Peter Bro Miltersen, Jaikumar Radhakrishnan and Ingo Wegener
622-631
A Basis of Tiling Motifs for Generating Repeated Patterns and Its Complexity for Higher Quorum
N. Pisanti, M. Crochemore, R. Grossi and M. -F. Sagot
632-641
On the Complexity of Some Equivalence Problems for Propositional Calculi
Steffen Reith
642-651
Quantified Mu-Calculus for Control Synthesis
Stéphane Riedweg and Sophie Pinchinat
652-661
On Probabilistic Quantified Satisfiability Games
Marcin Rychlik
662-670
A Completeness Property of Wilke’s Tree Algebras
Saeed Salehi
671-680
Symbolic Topological Sorting with OBDDs
Philipp Woelfel
681-690
Ershov’s Hierarchy of Real Numbers
Xizhong Zheng, Robert Rettinger and Romain Gengler
Back matter