Fourth IFIP International Conference on Theoretical Computer Science - TCS 2006

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 TOC:Locality of Queries and Transformations.- RDF as a Data Model.- Recursion and Probability.- Distributed Algorithms for Autonomous Mobile Robots.- Variations on an Ordering Theme with Constraints.- An Algorithm to Reduce the Communication Traffic for Multi-Word Searches in a Distributed Hash Table.- Fast Cellular Automata with Restricted Inter-Cell Communication.- Decidable Properties for Regular Cellular Automa.- Regular Hedge Model Checking.- Spectral Partitioning of Random Graphs with Given Expected Degrees.- On PTAS for Planar Graph Problems.