SOFSEM 2006: Theory and Practice of Computer Science

This book presents the proceedings of the 32nd Conference on Current Trends in Theory and Practice of Computer Science, held in Merin, Czech Republic. The 45 revised full papers, presented together with 10 invited contributions were carefully reviewed and selected from 157 submissions. The papers were organized in four topical tracks on computer science foundations, wireless, mobile, ad hoc and sensor networks, database technologies, and semantic Web technologies.

Inhalt

Invited Talks.- How Can Nature Help Us Compute?.- Evolving Ontology Evolution.- A Formal Comparison of Visual Web Wrapper Generators.- Beyond the Horizon: Planning Future European ICT R&D.- Selfish Routing in Networks.- New Physics and Hypercomputation.- Models and Algorithms for Wireless Sensor Networks (Smart Dust).- SomeWhere in the Semantic Web.- Mobility in Wireless Networks.- Group Communication: From Practice to Theory.- Regular Papers.- A General Data Reduction Scheme for Domination in Graphs.- Incremental Method for XML View Maintenance in Case of Non Monitored Data Sources.- Non-intersecting Complexity.- Constructing Interference-Minimal Networks.- Matching Points with Rectangles and Squares.- Searching Paths of Constant Bandwidth.- Graph Searching and Search Time.- Reasoning About Inconsistent Concurrent Systems: A Non-classical Temporal Logic.- Simple Algorithm for Sorting the Fibonacci String Rotations.- Oriented Coloring: Complexity and Approximation.- nonblocker: Parameterized Algorithmics for minimum dominating set.- Quantum Finite Automata and Logics.- FDSI-Tree: A Fully Distributed Spatial Index Tree for Efficient & Power-Aware Range Queries in Sensor Networks.- Roman Domination: A Parameterized Perspective.- Sedna: A Native XML DBMS.- Optimal Memory Rendezvous of Anonymous Mobile Agents in a Unidirectional Ring.- The Knowledge Cartography - A New Approach to Reasoning over Description Logics Ontologies.- Complexity and Exact Algorithms for Multicut.- Using Extensible Heterogeneous Database Transformers.- P-Selectivity, Immunity, and the Power of One Bit.- Transparent Migration of Database Services.- Merging and Merge-Sort in a Single Hop Radio Network.- On Optimal and Efficient in Place Merging.- A Personalized Recommendation System Based on PRML for E-Commerce.- An Efficient Index Scheme for XML Databases.- On Separating Constant from Polynomial Ambiguity of Finite Automata.- Reliable Broadcasting Without Collision Detection.- Semi-strong Static Type Checking of Object-Oriented Query Languages.- Building a Fuzzy Transformation System.- News Generating Via Fuzzy Summarization of Databases.- Improving Web Sites with Web Usage Mining, Web Content Mining, and Semantic Analysis.- Automatic Distribution of Sequential Code Using JavaSymphony Middleware.- Unifying Framework for Message Passing.- Heuristics on the Definition of UML Refinement Patterns.- The Complexity of Problems on Implicitly Represented Inputs.- How Many Dots Are Really Needed for Head-Driven Chart Parsing?.- Ontology Acquisition for Automatic Building of Scientific Portals.- Improved ROCK for Text Clustering Using Asymmetric Proximity.- Compact Encodings for All Local Path Information in Web Taxonomies with Application to WordNet.- Computational Complexity of Relay Placement in Sensor Networks.- On the NP-Completeness of Some Graph Cluster Measures.- A Flexible Policy Architecture for Mobile Agents.- An Improved Digital Signature with Message Recovery Using Self-certified Public Keys Without Trustworthy System Authority.- Small Independent Edge Dominating Sets in Graphs of Maximum Degree Three.- The Best Student Paper.- Level-of-Detail in Behaviour of Virtual Humans.