Skip to main content
SpringerLink
Log in
Book cover

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

  • Conference proceedings
  • © 2006

Overview

Editors:
  1. Gonzalo Navarro

    1. Universidad de Chile, Chile

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Leopoldo Bertossi

    1. Carleton University, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Yoshiharu Kohayakawa

    1. Universidade de Sao Paulo, Brazil

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Presents the most current research in Information and Communication Technologies
  • Includes supplementary material: sn.pub/extras

Part of the book series: IFIP Advances in Information and Communication Technology (IFIPAICT, volume 209)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (24 papers)

  1. Front Matter

    Pages I-XII
    Download chapter PDF

  2. Invited Talks

    1. Front Matter

      Pages 1-1
      Download chapter 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
      Download chapter 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
      Download chapter 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
Back to top

Keywords

About this book

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).

Editors and Affiliations

  • Universidad de Chile, Chile

    Gonzalo Navarro

  • Carleton University, Canada

    Leopoldo Bertossi

  • Universidade de Sao Paulo, Brazil

    Yoshiharu Kohayakawa

Bibliographic Information

  • Book Title: Fourth IFIP International Conference on Theoretical Computer Science - TCS 2006

  • Book Subtitle: IFIP 19th World Computer Congress, TC-1, Foundations of Computer Science, August 23-24, 2006, Santiago, Chile

  • Editors: Gonzalo Navarro, Leopoldo Bertossi, Yoshiharu Kohayakawa

  • Series Title: IFIP Advances in Information and Communication Technology

  • DOI: https://doi.org/10.1007/978-0-387-34735-6

  • Publisher: Springer New York, NY

  • eBook Packages: Computer Science, Computer Science (R0)

  • Copyright Information: IFIP International Federation for Information Processing 2006

  • Hardcover ISBN: 978-0-387-34633-5Published: 16 August 2006

  • Softcover ISBN: 978-1-4899-9050-1Published: 06 December 2014

  • eBook ISBN: 978-0-387-34735-6Published: 15 December 2006

  • Series ISSN: 1868-4238

  • Series E-ISSN: 1868-422X

  • Edition Number: 1

  • Number of Pages: XII, 315

  • Topics: Theory of Computation, Computer Science, general

Publish with us

Policies and ethics

Back to top

Search

Navigation