Randomized Communication Protocols (A Survey) / Juraj Hromkovič
Optimal Mutation Rate UsingBayesian Priors for Estimation of Distribution Algorithms / Thilo Mahnig ; Heinz Mühlenbein
An Experimental Assessment of a Stochastic, Anytime, Decentralized, Soft Colourer for Sparse Graphs / Stephen Fitzpatrick ; Lambert Meertens
Randomized BranchingPrograms / Martin Sauerhoff
Yet Another Local Search Method for Constraint Solving / Philippe Codognet ; Daniel Diaz
An Evolutionary Algorithm for the Sequence Coordination in Furniture Production / Carlo Meloni
Evolutionary Search for Smooth Maps in Motor Control Unit Calibration / Jan Poland ; Kosmas Knödler ; Alexander Mitterer ; Thomas Fleischhauer ; Frank Zuber-Goos ; Andreas Zell
Some Notes on Random Satisfiability / Gregory B. Sorkin
Prospects for Simulated AnnealingAlgorithms in Automatic Differentiation / Uwe Naumann ; Peter Gottschling
Optimization and Simulation: Sequential Packingof Flexible Objects Using Evolutionary Algorithms / Henning Behnke ; Michael Kolonko ; Ulrich Mertins ; Stefan Schnitter
Distributed Quantum Computing / Harry Buhrman ; Hein Röhrig
Selfish Routing in Non-cooperative Networks: A Survey / R. Feldmann ; M. Gairing ; Thomas Lücking ; Burkhard Monien ; Manuel Rode
Process Algebraic Frameworks for the Specification and Analysis of Cryptographic Protocols / Roberto Gorrieri ; Fabio Martinelli
Semantic and Syntactic Approaches to Simulation Relations / Jo Hannay ; Shin-ya Katsumata ; Donald Sannella
On the Computational Complexity of Conservative Computing / Giancarlo Mauri ; Alberto Leporati
Constructing Infinite Graphs with a Decidable MSO-Theory / Wolfgang Thomas
Towards a Theory of Randomized Search Heuristics / Ingo Wegener
Contributed Papers
Adversarial Models for Priority-Based Networks|C. Álvarez / M. Blesa ; J. Díaz ; A. Fernández ; M. Serna
On Optimal Merging Networks / Kazuyuki Amano ; Akira Maruoka
Problems which Cannot Be Reduced to Any Proper Subproblems / Klaus Ambos-Spies
ACID-Unification Is NEXPTIME-Decidable / Siva Anantharaman ; Paliath Narendran ; Michael Rusinowitch
Completeness in Differential Approximation Classes / G. Ausiello ; C. Bazgan ; M. Demange ; V. Th. Paschos
On the Length of the Minimum Solution of Word Equations in One Variable / Kensuke Baba ; Satoshi Tsuruta ; Ayumi Shinohara ; Masayuki Takeda
Smoothed Analysis of Three Combinatorial Problems / Cyril Banderier ; René Beier ; Kurt Mehlhorn
Inferring Strings from Graphs and Arrays / Hideo Bannai ; Shunsuke Inenaga
Faster Algorithms for k-Medians in Trees / Robert Benkoczi ; BinayBhattacharya ; MarekChrobak ; Lawrence L. Larmore ; Wojciech Rytter
Periodicity and Transitivity for Cellular Automata in BesicovitchTopologies / F.Blanchard ; J.Cervelle ; E. Formenti
Starting with Nondeterminism: The Systematic Derivation of Linear-Time Graph Layout Algorithms / Hans L. Bodlaender ; Michael R. Fellows ; Dimitrios M. Thilikos 239
Error-Bounded Probabilistic Computations between MA and AM / Elmar Böhler ; Christian Glaßer ; Daniel Meister
A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves / Paul S. Bonsma ; Tobias Brueggemann ; Gerhard J. Woeginger
Symbolic Analysis of Crypto-Protocols Based on Modular Exponentiation / Michele Boreale ; Maria Grazia Buscemi
Denotational Testing Semantics in Coinductive Form / Michele Boreale and Fabio Gadducci
Lower Bounds for General Graph-Driven Read-Once Parity Branching Programs / Henrik Brosenne ; Matthias Homeister ; Stephan Waack
The Minimal Graph Model of Lambda Calculus / Antonio Bucciarelli and Antonino Salibra
Unambiguous Automata on Bi-infinite Words / Olivier Carton
Relating Hierarchy of Temporal Properties to Model Checking / Ivana Černá ; Radek Pelánek
Stochastic Algorithms for Gene Expression Analysis (Invited Talk) / Lucila Ohno-Machado ; Winston Patrick Kuo
Analysis of a Randomized Local Search Algorithm for LDPCC Decoding Problem / Osamu Watanabe ; Takeshi Sawai ; Hayato Takahashi
Testing a Simulated Annealing Algorithm in a Classification Problem / Karsten Luebke ; Claus Weihs
Global Search through Sampling Using a PDF / Benny Raphael ; Ian F.C. Smith
Simulated Annealing for Optimal Pivot Selection in Jacobian Accumulation / Uwe Naumann ; Peter Gottschling
Quantum Data Compression (Invited Talk) / John A. Vaccaro ; Yasuyoshi Mitsumori ; Stephen M. Barnett ; Erika Andersson ; Atsushi Hasegawa ; Masahiro Takeoka ; Masahide Sasaki
WhoÆs The Weakest Link? / Nikhil Devanur ; Richard J. Lipton ; Nisheeth Vishnoi
On the Stochastic Open Shop Problem / Roman A. Koryakin
Global Optimization - Stochastic or Deterministic? / Mike C. Bartholomew-Biggs ; Steven C. Parkhurst ; Simon P. Wilson
Two-Component Traffic Modelled by Cellular Automata: Imposing Passing Restrictions on Slow Vehicles Increases the Flow / Paul Baalham ; Ole Steuernagel
Average-Case Complexity of Partial Boolean Functions / Alexander Chashkin
Classes of Binary Rational Distributions Closed under Discrete Transformations / Roman Kolpakov
Author Index
Prospects of Quantum Informatics (Invited Talk) / Roland Kirschner
A Converging ACO Algorithm for Stochastic Combinatorial Optimization / Walter J. Gutjahr
AGILE: Software Architecture for Mobility / L. Andrade ; P. Baldan ; H. Baumeister ; R. Bruni ; A. Corradini ; R. De Nicola ; J.L. Fiadeiro ; F. Gadducci ; S. Gnesi ; P. Hoffman ; N. Koch ; P. Kosiuczenko ; A. Lapadula ; D. Latella ; A. Lopes ; M. Loreti ; M. Massink ; F. Mazzanti ; U. Montanari ; C. Oliveira ; R. Pugliese ; A. Tarlecki ; M. Wermelinger ; M. Wirsing ; A. Zawlocki
A Coinductive Calculus of Component Connectors / F. Arbab ; J.J.M.M. Rutten
An Attempt at Analysing the Consistency Problems in the UML from a Classical Algebraic Viewpoint / E. Astesiano ; G. Reggio
MultiMedia Instruction in Safe and Secure Systems / B. Krieg-Bruckner ; D. Hutter ; A. Lindow ; C. Luth ; A. Mahnke ; E. Melis ; P. Meier ; A. Poetzsch-Heffter ; M. Roggenbach ; G. Russell ; J.-G. Smaus
Invited Non-technical Papers
Zero, Connected, Empty / R.A. Goguen ; J.A. Goguen
Zero, Connected, Empty: An Essay after a Cantata
Contributed Papers
Type Checking Parametrised Programs and Specifications in ASL+FPC / D. Aspinall
Pre-nets, Read Arcs and Unfolding: A Functorial Presentation
Coreflective Concurrent Semantics for Single-Pushout Graph Grammars / L. Ribeiro
Completeness Results for Fibred Parchments / C. Caleiro ; P. Gouveia ; J. Ramos
Use of Patterns in Formal Development: Systematic Transition from Problems to Architectural Designs / C. Choppy ; M. Heisel
Conditional Circular Coinductive Rewriting with Case Analysis / K. Lin ; G. Rosu
Algebraic Higher-Order Nets: Graphs and Petri Nets as Tokens / K. Hoffmann ; T. Mossakowski
The Coinductive Approach to Verifying Cryptographic Protocols / J. Hughes ; M. Warnier
Behavioural Equivalence and Indistinguishability in Higher-Order Typed Languages / S. Katsumata
Approach-Independent Structuring Concepts for Rule-Based Systems / H.-J. Kreowski ; S. Kuske
Notions of Behaviour and Reachable-Part and Their Institutions / A. Kurz
Combining Specification Formalisms in the `General Logic' of Multialgebras / Y. Lamo ; M. Walicki
On How Distribution and Mobility Interfere with Coordination
Foundations of Heterogeneous Specification
Algebraic-Coalgebraic Specification in CoCasl / H. Reichel ; L. Schroder
Translating Logics for Coalgebras / D. Pattinson
Presenting and Combining Inference Systems / W. Pawlowski
Monad-Independent Dynamic Logic in HasCasl / L. Schröder
Preserving Properties in System Redesign: Rule-Based Approach / M. Urbasek
Author Index
Invited Technical Papers
AGILE: Software Architecture for Mobility / L. Andrade ; P. Baldan ; H. Baumeister ; R. Bruni ; A. Corradini ; R. De Nicola ; J.L. Fiadeiro ; F. Gadducci ; S. Gnesi ; P. Hoffman ; N. Koch ; P. Kosiuczenko ; A. Lapadula ; D. Latella ; A. Lopes ; M. Loreti ; M. Massink ; F. Mazzanti ; U. Montanari ; C. Oliveira ; R. Pugliese ; A. Tarlecki ; M. Wermelinger ; M. Wirsing ; A. Zawlocki
A Coinductive Calculus of Component Connectors / F. Arbab ; J.J.M.M. Rutten
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
図書
