SOFSEM 2010: Theory and Practice of Computer Science

This volume contains the invited and contributed papers selected for presen- tion at SOFSEM 2010, the 36th Conference on Current Trends in Theory and Practiceof Computer Science, held January23–29,2010 in the Hotel Bed? richov, ? Spindler? uv Mlyn, ´ of the Krkono? se Mountains of the Czech Republic. SOFSEM(originally:SOFtwareSEMinar)isdevotedtoleadingresearch,and fosters the cooperation among researchers and professionals from academia and industry in all areas of computer science. As a well-established and fully int- national conference, SOFSEM maintains the best of its original Winter School aspects,suchasa highnumber of invitedtalksandanin-depth coverageofnovel research results in selected areas within computer science. SOFSEM 2010 was organized around the following four tracks: – Foundations of Computer Science (Chairs: David Peleg, Anca Muscholl) – Principles of Software Construction (Chair: Bernhard Rumpe) – Data, Knowledge, and Intelligent Systems (Chair: Jaroslav Pokorn´ y) – Web Science (Chair: Jan van Leeuwen) With these tracks, SOFSEM 2010 covered the latest advances in research, both theoretical and applied, in leading areas of computer science. The SOFSEM 2010 Program Committee consisted of 78 international experts from 20 di?erent countries, representing the track areas with outstanding expertise. An integral part of SOFSEM 2010 was the traditional Student Research - rum (SRF, Chair: Ma ´ria Bielikov´ a), organized with the aim to present student projects in the theory and practice of computer science and to give students feedback on both the originality of their scienti?c results and on their work in progress.

Invited Talks.- Forcing Monotonicity in Parameterized Verification: From Multisets to Words.- Research Issues in the Automated Testing of Ajax Applications.- Essential Performance Drivers in Native XML DBMSs.- Continuous Processing of Preference Queries in Data Streams.- Clock Synchronization: Open Problems in Theory and Practice.- Regret Minimization and Job Scheduling.- Lessons in Software Evolution Learned by Listening to Smalltalk.- The Web of Things: Extending the Web into the Real World.- Web Science: The Digital-Heritage Case.- Model-Driven Software Product Line Testing: An Integrated Approach.- Taming the Complexity of Inductive Logic Programming.- Regular Papers.- A Rule Format for Unit Elements.- Approximability of Edge Matching Puzzles.- A Linear Time Algorithm for Finding Three Edge-Disjoint Paths in Eulerian Networks.- R-Programs: A Framework for Distributing XML Structural Joins across Function Calls.- Fast Arc-Annotated Subsequence Matching in Linear Space.- Automated Deadlock Detection in Synchronized Reentrant Multithreaded Call-Graphs.- A Kernel for Convex Recoloring of Weighted Forests.- Symbolic OBDD-Based Reachability Analysis Needs Exponential Space.- A Social Vision of Knowledge Representation and Reasoning.- Flavors of KWQL, a Keyword Query Language for a Semantic Wiki.- On Pattern Density and Sliding Block Code Behavior for the Besicovitch and Weyl Pseudo-distances.- On a Labeled Vehicle Routing Problem.- Improved Matrix Interpretation.- Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays.- Query Optimization through Cached Queries for Object-Oriented Query Language SBQL.- Perfect Matching for Biconnected Cubic Graphs in O(n log2 n) Time.- Destructive Rule-Based Properties and First-Order Logic.- Learning User Preferences for 2CP-Regression for a Recommender System.- Parallel Randomized Load Balancing: A Lower Bound for a More General Model.- Ant-CSP: An Ant Colony Optimization Algorithm for the Closest String Problem.- Linear Complementarity Algorithms for Infinite Games.- Mixing Coverability and Reachability to Analyze VASS with One Zero-Test.- Practically Applicable Formal Methods.- Fast and Compact Prefix Codes.- New Results on the Complexity of Oriented Colouring on Restricted Digraph Classes.- Smooth Optimal Decision Strategies for Static Team Optimization Problems and Their Approximations.- Algorithms for the Minimum Edge Cover of H-Subgraphs of a Graph.- On the Complexity of the Highway Pricing Problem.- Accelerating Smart Play-Out.- Optimum Broadcasting in Complete Weighted-Vertex Graphs.- On Contracting Graphs to Fixed Pattern Graphs.- Dynamic Edit Distance Table under a General Weighted Cost Function.- How to Complete an Interactive Configuration Process?.- Design Patterns Instantiation Based on Semantics and Model Transformations.- A Complete Symbolic Bisimulation for Full Applied Pi Calculus.- OTwig: An Optimised Twig Pattern Matching Approach for XML Databases.- Picture Recognizability with Automata Based on Wang Tiles.- Unilateral Orientation of Mixed Graphs.- Maintaining XML Data Integrity in Programs.- Improving Classification Performance with Focus on the Complex Areas.- CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions.- Source Code Rejuvenation Is Not Refactoring.- Empirical Evaluation of Strategies to Detect Logical Change Dependencies.- Efficient Testing of Equivalence of Words in a Free Idempotent Semigroup.- An Amortized Search Tree Analysis for k-Leaf Spanning Tree.- Approximate Structural Consistency.- Comprehensive System for Systematic Case-Driven Software Reuse.- Comparison of Scoring and Order Approach in Description Logic .- Homophily of Neighborhood in Graph Relational Classifier.- Multilanguage Debugger Architecture.- Student Groups Modeling by Integrating Cluster Representation and Association Rules Mining.- Finding and Certifying Loops.- Vertex Ranking with Capacity.