4. IFIP TCS 2006: Santiago, Chile

Gonzalo Navarro, Leopoldo E. Bertossi, Yoshiharu Kohayakawa (Eds.): 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. IFIP 209 Springer 2006, ISBN 0-387-34633-3

Invited Talks

Marcelo Arenas:
Locality of Queries and Transformations. 3
Jozef Gruska:
From Informatics to Quantum Informatics. 5
Claudio Gutiérrez:
RDF as a Data Model. 7
Marcos A. Kiwi:
Adversarial Queueing Theory Revisited. 9-10
Nicola Santoro:
Distributed Algorithms for Autonomous Mobile Robots. 11
Mihalis Yannakakis:
Recursion and Probability. 13

Invited Papers

Jozef Gruska:
From Informatics to Quantum Informatics. 17-46
Giuseppe Prencipe, Nicola Santoro:
Distributed Algorithms for Autonomous Mobile Robots. 47-62

Contributed Papers

Brian C. Dean, Michel X. Goemans, Nicole Immorlica:
The Unsplittable Stable Marriage Problem. 65-75
Walter Guttmann, Markus Maucher:
Variations on an Ordering Theme with Constraints. 77-90
Luca Bortolussi, Francesco Fabris, Alberto Policriti:
BuST-Bundled Suffix Trees. 91-102
Andrej Brodnik, Johan Karlsson, J. Ian Munro, Andreas Nilsson:
An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture. 103-114
Yuichi Sei, Kazutaka Matsuzaki, Shinichi Honiden:
An Algorithm to Reduce the Communication Traffic for Multi-Word Searches in a Distributed Hash Table. 115-129
Stefan Dobrev, Paola Flocchini, Rastislav Kralovic, Nicola Santoro:
Exploring an Unknown Graph to Locate a Black Hole Using Tokens. 131-150
Martin Kutrib, Andreas Malcher:
Fast Cellular Automata with Restricted Inter-Cell Communication: Computational Capacity. 151-164
Denis Caromel, Ludovic Henrio:
Asynchonous Distributed Components: Concurrency and Determinacy. 165-183
Pietro di Lena:
Decidable Properties for Regular Cellular Automata. 185-196
Thierry Jéron, Hervé Marchand, Vlad Rusu:
Symbolic Determinisation of Extended Automata. 197-212
Julien d'Orso, Tayssir Touili:
Regular Hedge Model Checking. 213-230
Stephen L. Bloom, Zoltán Ésik:
Completing Categorical Algebras. 231-249
Hans-Joachim Böckenhauer, Luca Forlizzi, Juraj Hromkovic, Joachim Kneis, Joachim Kupke, Guido Proietti, Peter Widmayer:
Reusing Optimal TSP Solutions for Locally Modified Input Instances. 251-270
Amin Coja-Oghlan, Andreas Goerdt, André Lanka:
Spectral Partitioning of Random Graphs with Given Expected Degrees. 271-282
Marco Abraham, Rolf Kötter, Antje Krumnack, Egon Wanke:
A Connectivity Rating for Vertices in Networks. 283-298
Xiuzhen Huang, Jianer Chen:
On PTAS for Planar Graph Problems. 299-313