IFIP TC6 Open Digital Library

4. IFIP TCS 2006: Santiago, Chile

Fourth IFIP International Conference on Theoretical Computer Science (TCS 2006), IFIP 19th World Computer Congress, TC-1 Foundations of Computer Science, August 23-24, 2006, Santiago, Chile

Gonzalo Navarro, Leopoldo E. Bertossi, Yoshiharu Kohayakawa

Springer, IFIP 209, ISBN: 0-387-34633-3



Contents

Invited Talks

Locality of Queries and Transformations.

Marcelo Arenas

 3

From Informatics to Quantum Informatics.

Jozef Gruska

 5

RDF as a Data Model.

Claudio Gutiérrez

 7

Adversarial Queueing Theory Revisited.

Marcos A. Kiwi

 9-10

Distributed Algorithms for Autonomous Mobile Robots.

Nicola Santoro

 11

Recursion and Probability.

Mihalis Yannakakis

 13

Invited Papers

From Informatics to Quantum Informatics.

Jozef Gruska

 17-46

Distributed Algorithms for Autonomous Mobile Robots.

Giuseppe Prencipe, Nicola Santoro

 47-62

Contributed Papers

The Unsplittable Stable Marriage Problem.

Brian C. Dean, Michel X. Goemans, Nicole Immorlica

 65-75

Variations on an Ordering Theme with Constraints.

Walter Guttmann, Markus Maucher

 77-90

BuST-Bundled Suffix Trees.

Luca Bortolussi, Francesco Fabris, Alberto Policriti

 91-102

An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture.

Andrej Brodnik, Johan Karlsson, J. Ian Munro, Andreas Nilsson

 103-114

An Algorithm to Reduce the Communication Traffic for Multi-Word Searches in a Distributed Hash Table.

Yuichi Sei, Kazutaka Matsuzaki, Shinichi Honiden

 115-129

Exploring an Unknown Graph to Locate a Black Hole Using Tokens.

Stefan Dobrev, Paola Flocchini, Rastislav Kralovic, Nicola Santoro

 131-150

Fast Cellular Automata with Restricted Inter-Cell Communication: Computational Capacity.

Martin Kutrib, Andreas Malcher

 151-164

Asynchonous Distributed Components: Concurrency and Determinacy.

Denis Caromel, Ludovic Henrio

 165-183

Decidable Properties for Regular Cellular Automata.

Pietro di Lena

 185-196

Symbolic Determinisation of Extended Automata.

Thierry Jéron, Hervé Marchand, Vlad Rusu

 197-212

Regular Hedge Model Checking.

Julien d'Orso, Tayssir Touili

 213-230

Completing Categorical Algebras.

Stephen L. Bloom, Zoltán Ésik

 231-249

Reusing Optimal TSP Solutions for Locally Modified Input Instances.

Hans-Joachim Böckenhauer, Luca Forlizzi, Juraj Hromkovic, Joachim Kneis, Joachim Kupke, Guido Proietti, Peter Widmayer

 251-270

Spectral Partitioning of Random Graphs with Given Expected Degrees.

Amin Coja-Oghlan, Andreas Goerdt, André Lanka

 271-282

A Connectivity Rating for Vertices in Networks.

Marco Abraham, Rolf Kötter, Antje Krumnack, Egon Wanke

 283-298

On PTAS for Planar Graph Problems.

Xiuzhen Huang, Jianer Chen

 299-313