SOFSEM 2010: Theory and Practice of Computer Science: 36th Conference on Current Trends in Theory and Practice of Computer Science, à pindlerův Mlýn, Czech Republic, January 23-29, 2010. Proceedings

This book constitutes the refereed proceedings of the 36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010, held in � pindleruv Mlýn, Czech Republic, in January 2009. The 53 revised full papers, presented together with 11 invited contributions, were carefully reviewed and selected from 134 submissions. SOFSEM 2010 was organized around the following four tracks: Foundations of computer science, principles of software construction, Data, knowledge, and intelligent systems and Web science. Content: Front Matter....Pages - Forcing Monotonicity in Parameterized Verification: From Multisets to Words....Pages 1-15 Research Issues in the Automated Testing of Ajax Applications....Pages 16-28 Essential Performance Drivers in Native XML DBMSs....Pages 29-46 Continuous Processing of Preference Queries in Data Streams....Pages 47-60 Clock Synchronization: Open Problems in Theory and Practice....Pages 61-70 Regret Minimization and Job Scheduling....Pages 71-76 Lessons in Software Evolution Learned by Listening to Smalltalk....Pages 77-95 The Web of Things: Extending the Web into the Real World....Pages 96-107 Web Science: The Digital-Heritage Case....Pages 108-111 Model-Driven Software Product Line Testing: An Integrated Approach....Pages 112-131 Taming the Complexity of Inductive Logic Programming....Pages 132-140 A Rule Format for Unit Elements....Pages 141-152 Approximability of Edge Matching Puzzles....Pages 153-164 A Linear Time Algorithm for Finding Three Edge-Disjoint Paths in Eulerian Networks....Pages 165-175 R-Programs: A Framework for Distributing XML Structural Joins across Function Calls....Pages 176-187 Fast Arc-Annotated Subsequence Matching in Linear Space....Pages 188-199 Automated Deadlock Detection in Synchronized Reentrant Multithreaded Call-Graphs....Pages 200-211 A Kernel for Convex Recoloring of Weighted Forests....Pages 212-223 Symbolic OBDD-Based Reachability Analysis Needs Exponential Space....Pages 224-234 A Social Vision of Knowledge Representation and Reasoning....Pages 235-246 Flavors of KWQL, a Keyword Query Language for a Semantic Wiki....Pages 247-258 On Pattern Density and Sliding Block Code Behavior for the Besicovitch and Weyl Pseudo-distances....Pages 259-270 On a Labeled Vehicle Routing Problem....Pages 271-282 Improved Matrix Interpretation....Pages 283-295 Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays....Pages 296-307 Query Optimization through Cached Queries for Object-Oriented Query Language SBQL....Pages 308-320 Destructive Rule-Based Properties and First-Order Logic....Pages 321-333 Learning User Preferences for 2CP-Regression for a Recommender System....Pages 334-345 Parallel Randomized Load Balancing: A Lower Bound for a More General Model....Pages 346-357 Ant-CSP: An Ant Colony Optimization Algorithm for the Closest String Problem....Pages 358-369 Linear Complementarity Algorithms for Infinite Games....Pages 370-381 Mixing Coverability and Reachability to Analyze VASS with One Zero-Test....Pages 382-393 Practically Applicable Formal Methods....Pages 394-406 Fast and Compact Prefix Codes....Pages 407-418 New Results on the Complexity of Oriented Colouring on Restricted Digraph Classes....Pages 419-427 Smooth Optimal Decision Strategies for Static Team Optimization Problems and Their Approximations....Pages 428-439 Algorithms for the Minimum Edge Cover of H-Subgraphs of a Graph....Pages 440-451 On the Complexity of the Highway Pricing Problem....Pages 452-464 Accelerating Smart Play-Out....Pages 465-476 Optimum Broadcasting in Complete Weighted-Vertex Graphs....Pages 477-488 On Contracting Graphs to Fixed Pattern Graphs....Pages 489-502 Dynamic Edit Distance Table under a General Weighted Cost Function....Pages 503-514 How to Complete an Interactive Configuration Process?....Pages 515-527 Design Patterns Instantiation Based on Semantics and Model Transformations....Pages 528-539 A Complete Symbolic Bisimulation for Full Applied Pi Calculus....Pages 540-551 OTwig: An Optimised Twig Pattern Matching Approach for XML Databases....Pages 552-563 Picture Recognizability with Automata Based on Wang Tiles....Pages 564-575 Unilateral Orientation of Mixed Graphs....Pages 576-587 Maintaining XML Data Integrity in Programs....Pages 588-599 Improving Classification Performance with Focus on the Complex Areas....Pages 600-611 CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions....Pages 612-626 Source Code Rejuvenation Is Not Refactoring....Pages 627-638 Empirical Evaluation of Strategies to Detect Logical Change Dependencies....Pages 639-650 Efficient Testing of Equivalence of Words in a Free Idempotent Semigroup....Pages 651-662 An Amortized Search Tree Analysis for k-Leaf Spanning Tree....Pages 663-671 Approximate Structural Consistency....Pages 672-684 Comprehensive System for Systematic Case-Driven Software Reuse....Pages 685-696 Homophily of Neighborhood in Graph Relational Classifier....Pages 697-708 Multilanguage Debugger Architecture....Pages 709-720 Student Groups Modeling by Integrating Cluster Representation and Association Rules Mining....Pages 721-730 Finding and Certifying Loops....Pages 731-742 Vertex Ranking with Capacity....Pages 743-754 Back Matter....Pages 755-766 ....Pages 767-778 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 This book constitutes the refereed proceedings of the 36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010, held in Špindleruv Mlýn, Czech Republic, in January 2009. The 53 revised full papers, presented together with 11 invited contributions, were carefully reviewed and selected from 134 submissions. SOFSEM 2010 was organized around the following four tracks: Foundations of computer science, principles of software construction, Data, knowledge, and intelligent systems and Web science