Fourth IFIP International Conference on Theoretical Computer Science - TCS 2006

1. Front Matter

   Pages I-XII

   PDF

2. Invited Talks

   1. Front Matter

      Pages 1-1

      PDF

   2. Locality of Queries and Transformations

      • Marcelo Arenas

      Pages 3-3

   3. From Informatics to Quantum Informatics

      • Jozef Gruska

      Pages 5-5

   4. RDF as a Data Model

      • Claudio Gutièrrez

      Pages 7-7

   5. Adversarial Queueing Theory Revisited

      • Marcos Kiwi

      Pages 9-10

   6. Distributed Algorithms for Autonomous Mobile Robots

      • Nicola Santoro

      Pages 11-11

   7. Recursion and Probability

      • Mihalis Yannakakis

      Pages 13-13

3. Invited Papers

   1. Front Matter

      Pages 15-15

      PDF

   2. From Informatics to Quantum Informatics

      • Jozef Gruska

      Pages 17-46

   3. Distributed Algorithms for Autonomous Mobile Robots

      • Giuseppe Prencipe, Nicola Santoro

      Pages 47-62

4. Contributed Papers

   1. Front Matter

      Pages 63-63

      PDF

   2. The Unsplittable Stable Marriage Problem

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

      Pages 65-75

   3. Variations on an Ordering Theme with Constraints

      • Walter Guttmann, Markus Maucher

      Pages 77-90

   4. BuST-Bundled Suffix Trees

      • Luca Bortolussi, Francesco Fabris, Aberto Policriti

      Pages 91-102

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

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

      Pages 103-114

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

      • Yuichi Sei, Kazutaka Matsuzaki, Shinichi Honiden

      Pages 115-129

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

      • Stefan Dobrev, Paola Flocchini, Rastislav Královič, Nicola Santoro

      Pages 131-150

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

      • Martin Kutrib, Andreas Malcher

      Pages 151-164

   9. Asynchonous Distributed Components: Concurrency and Determinacy

      • Denis Caromel, Ludovic Henrio

      Pages 165-183

The papers contained in this volume were presented at the fourth edition of the IFIP International Conference on Theoretical Computer Science (IFIP TCS), held August 23-24, 2006 in Santiago, Chile. They were selected from 44 pa­ pers submitted from 17 countries in response to the call for papers. A total of 16 submissions were accepted as full papers, yielding an acceptance rate of about 36%. Papers sohcited for IFIP TCS 2006 were meant to constitute orig­ inal contributions in two general areas: Algorithms, Complexity and Models of Computation; and Logic, Semantics, Specification and Verification. The conference also included six invited presentations: Marcelo Arenas (P- tificia Universidad Catolica de Chile, Chile), Jozef Gruska (Masaryk University, Czech Republic), Claudio Gutierrez (Universidad de Chile, Chile), Marcos Kiwi (Universidad de Chile, Chile), Nicola Santoro (Carleton University, Canada), and Mihalis Yannakakis (Columbia University, USA). The abstracts of those presentations are included in this volume. In addition, Jozef Gruska and Nicola Santoro accepted our invitation to write full papers related to their talks. Those two surveys are included in the present volume as well. TCS is a biannual conference. The first edition was held in Sendai (Japan, 2000), followed by Montreal (Canada, 2002) and Toulouse (France, 2004).

• Automat
• algorithms
• artificial intelligence
• automata
• computer
• computer science
• model checking

• Universidad de Chile, Chile

  Gonzalo Navarro

• Carleton University, Canada

  Leopoldo Bertossi

• Universidade de Sao Paulo, Brazil

  Yoshiharu Kohayakawa

Policies and ethics