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.

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.