IFIP TC6 Open Digital Library

5. IFIP TCS 2008: Milano, Italy

Fifth IFIP International Conference On Theoretical Computer Science - TCS 2008, IFIP 20th World Computer Congress, TC 1, Foundations of Computer Science, September 7-10, 2008, Milano, Italy

Giorgio Ausiello, Juhani Karhumäki, Giancarlo Mauri, C.-H. Luke Ong

Springer, IFIP 273, ISBN: 978-0-387-09679-7



Contents

Track A

Invited talks

Ambiguity and Complementation in Recognizable Two-dimensional Languages.

Dora Giammarresi, Antonio Restivo

 5-20

Algorithmic Game Theory: Some Greatest Hits and Future Directions.

Tim Roughgarden

 21-42

Synchronizing Road Coloring.

A. N. Trahtman

 43-53

Contributed talks

Leader Election in Anonymous Rings: Franklin Goes Probabilistic.

Rena Bakhshi, Wan Fokkink, Jun Pang, Jaco van de Pol

 57-72

Inverse Problems Have Inverse Complexity.

Tobias Berg, Harald Hempel

 73-86

Literal Shuffle of Compressed Words.

Alberto Bertoni, Christian Choffrut, Roberto Radicioni

 87-100

Reconstructing words from a fixed palindromic length sequence.

Alexandre Blondin Massé, Srecko Brlek, Andrea Frosini, Sébastien Labbé, Simone Rinaldi

 101-114

The mv-decomposition: definition and application to the distance-2 broadcast problem in multi-hops radio networks.

Olivier Cogis, Benoît Darties, Sylvain Durand, Jean-Claude König, Geneviève Simonet

 115-126

Partitioning Random Graphs with General Degree Distributions.

Amin Coja-Oghlan, André Lanka

 127-141

On the Longest Common Factor Problem.

Maxime Crochemore, Alessandra Gabriele, Filippo Mignosi, Mauriana Pesaresi

 143-155

Stable Dynamics of Sand Automata.

Alberto Dennunzio, Pierre Guillon, Benoît Masson

 157-169

On tractability of Cops and Robbers game.

Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl

 171-185

Computability of Tilings.

Grégory Lafitte, Michael Weiss

 187-201

A Classification of Degenerate Loop Agreement.

Xingwu Liu, Juhua Pu, Jianzhong Pan

 203-213

On the expressive power of univariate equations over sets of natural numbers.

Alexander Okhotin, Panos Rondogiannis

 215-227

Collisions and their Catenations: Ultimately Periodic Tilings of the Plane.

Nicolas Ollinger, Gaétan Richard

 229-240

Cache-sensitive Memory Layout for Binary Trees.

Riku Saikkonen, Eljas Soisalon-Soininen

 241-255

Track B

Invited talks

From Processes to ODEs by Chemistry.

Luca Cardelli

 261-281

Differential Linear Logic and Processes.

Thomas Ehrhard

 283

Solving Monotone Polynomial Equations.

Javier Esparza, Stefan Kiefer, Michael Luttenberger

 285-298

Contributed talks

Lifting Non-Finite Axiomatizability Results to Extensions of Process Algebras.

Luca Aceto, Wan Fokkink, Anna Ingólfsdóttir, Mohammad Reza Mousavi

 301-316

Finite Equational Bases for Fragments of CCS with Restriction and Relabelling.

Luca Aceto, Anna Ingólfsdóttir, Bas Luttik, Paul van Tilburg

 317-332

µ-calculus Pushdown Module Checking with Imperfect State Information.

Benjamin Aminof, Axel Legay, Aniello Murano, Olivier Serre

 333-348

From Formal Proofs to Mathematical Proofs: A Safe, Incremental Way for Building in First-order Decision Procedures.

Frédéric Blanqui, Jean-Pierre Jouannaud, Pierre-Yves Strub

 349-365

On Traits and Types in a Java-like Setting.

Viviana Bono, Ferruccio Damiani, Elena Giachino

 367-382

Canonical Sequent Proofs via Multi-Focusing.

Kaustuv Chaudhuri, Dale Miller, Alexis Saurin

 383-396

Universal Coinductive Characterisations of Process Semantics.

David de Frutos-Escrig, Carlos Gregorio-Rodríguez

 397-412

Static and dynamic typing for the termination of mobile processes.

Romain Demangeon, Daniel Hirschkoff, Davide Sangiorgi

 413-427

Regular n-ary Queries in Trees and Variable Independence.

Emmanuel Filiot, Sophie Tison

 429-443

Hamiltonicity of automatic graphs.

Dietrich Kuske, Markus Lohrey

 445-459

Marking the chops: an unambiguous temporal logic.

Kamal Lodaya, Paritosh K. Pandya, Simoni S. Shah

 461-476

On Boundedness in Depth in the pi-Calculus.

Roland Meyer

 477-489

A Unified View of Tree Automata and Term Schematisations.

Nicolas Peltier

 491-505

Deconstructing behavioural theories of mobility.

Julian Rathke, Pawel Sobocinski

 507-520

Adequacy of Compositional Translations for Observational Semantics.

Manfred Schmidt-Schauß, Joachim Niehren, Jan Schwinghammer, David Sabel

 521-535

The Surprising Robustness of (Closed) Timed Automata against Clock-Drift.

Mani Swaminathan, Martin Fränzle, Joost-Pieter Katoen

 537-553