Fourth IFIP International Conference on Theoretical Computer Science - TCS 2006: IFIP 19th World Computer Congress, TC-1, Foundations of Computer Science, ... in Information and Communication Technology)

This volume presents proceedings from the 19th IFIP World Computer Congress in Santiago, Chile. The proceedings of the World Computer Congress are a product of the gathering of 2,000 delegates from more than 70 countries to discuss a myriad of topics in the ICT domain. Of particular note, this marks the first time that a World Computer Congress has been held in a Latin American country. Topics in this series include: - The 4th International Conference on Theoretical Computer Science - Education for the 21st Century- Impact of ICT and Digital Resources - Mobile and Wireless Communication Networks - Ad-Hoc Networking - Network Control and Engineering for QoS, Security, and Mobility - The Past and Future of Information Systems: 1976-2006 and Beyond - History of Computing and Education - Biologically Inspired Cooperative Computing - Artificial Intelligence in Theory and Practice - Applications in Artificial Intelligence - Advanced Software Engineering: Expanding the Frontiers of Software Contents......Page 10 Part I: Invited Talks......Page 12 Locality of Queries and Transformations......Page 13 From Informatics to Quantum Informatics......Page 14 RDF as a Data Model......Page 15 Adversarial Queueing Theory Revisited......Page 16 Distributed Algorithms for Autonomous Mobile Robots......Page 18 Recursion and Probability......Page 19 Part II: Invited Papers......Page 20 From Informatics to Quantum Informatics......Page 21 Distributed Algorithms for Autonomous Mobile Robots......Page 51 Part III: Contributed Papers......Page 67 The Unsplittable Stable Marriage Problem......Page 68 Variations on an Ordering Theme with Constraints......Page 79 BuST-Bundled Suffix Trees......Page 93 An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture......Page 105 An Algorithm to Reduce the Communication Traffic for Multi-Word Searches in a Distributed Hash Table......Page 117 Exploring an Unknown Graph to Locate a Black Hole Using Tokens......Page 132 Fast Cellular Automata with Restricted Inter-Cell Communication......Page 152 Asynchonous Distributed Components: Concurrency and Determinacy......Page 166 Decidable Properties for Regular Cellular Automata......Page 185 Symbolic Determinisation of Extended Automata......Page 197 Regular Hedge Model Checking......Page 213 Completing Categorical Algebras......Page 231 Reusing Optimal TSP Solutions for Locally Modified Input Instances......Page 250 Spectral Partitioning of Random Graphs with Given Expected Degrees......Page 270 A Connectivity Rating for Vertices in Networks......Page 282 On PTAS for Planar Graph Problems......Page 298 Index......Page 313 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). International Federation for Information Processing The IFIP series publishes state-of-the-art results in the sciences and technologies of information and communication. The scope of the series includes: foundations of computer science; software theory and practice; education; computer applications in technology; communication systems; systems modeling and optimization; information systems; computers and society; computer systems technology; security and protection in information processing systems; artificial intelligence; and human-computer interaction. Proceedings and post-proceedings of referred international conferences in computer science and interdisciplinary fields are featured. These results often precede journal publication and represent the most current research. The principal aim of the IFIP series is to encourage education and the dissemination and exchange of information about all aspects of computing. For more information about the 300 other books in the IFIP series, please visit www.springer.com. For more information about IFIP, please visit www.ifip.org.