SOFSEM 2010: Theory and Practice of Computer Science: 36th Conference on Current Trends in Theory and Practice of Computer Science, January 2010 Proceedings

by Jan van Leeuwen (Editor), Anca Muscholl (Editor), David Peleg (Editor), Jaroslav Pokorny (Editor), Bernhard Rumpe (Editor)

Overview

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.

Product Details

ISBN-13:	9783642112652
Publisher:	Springer Berlin Heidelberg
Publication date:	03/05/2010
Series:	Lecture Notes in Computer Science , #5901
Edition description:	2010
Pages:	780
Product dimensions:	6.10(w) x 9.30(h) x 1.10(d)

Table of Contents

Invited Talks

Forcing Monotonicity in Parameterized Verification: From Multisets to Words Parosk Aziz Abdulla 1

Research Issues in the Automated Testing of Ajax Applications Arie van Deursen Ali Mesbah 16

Essential Performance Drivers in Native XML DBMSs Theo Härder Christian Mathis Sebastian Bächle Karsten Schmidt Andreas M. Weiner 29

Continuous Processing of Preference Queries in Data Streams Maria Kontaki Apostolos N. Papadopoulos Yannis Manolopoulos 47

Clock Synchronization: Open Problems in Theory and Practice Christoph Lenzen Thomas Locher Philipp Sommer Roger Wattenhofer 61

Regret Minimization and Job Scheduling Yishay Mansour 71

Lessons in Software Evolution Learned by Listening to Smalltalk Oscar Nierstrasz Tudor Gîrba 77

The Web of Things: Extending the Web into the Real World Dave Raggett 96

Web Science: The Digital-Heritage Case Guus Schreiber 108

Model-Driven Software Product Line Testing: An Integrated Approach Andy Schürr Sebastian Oster Florian Markert 112

Taming the Complexity of Inductive Logic Programming Filip Železný Ondřej Kuželka 132

Regular Papers

A Rule Format for Unit Elements Luca Aceto Anna Ingolfsdottir MohammadReza Mousavi Michel A. Reniers 141

Approximability of Edge Matching Puzzles Antonios Antoniadis Andrzej Lingas 153

A Linear Time Algorithm for Finding Three Edge-Disjoint Paths in Eulerian Networks Maxim A. Babenko Ignat I. Kolesnichenko Ilya P. Razenshteyn 165

R-Programs: A Framework for Distributing XML Structural Joins across Function Calls David Bednárek 176

Fast Arc-Annotated Subsequence Matching in Linear Space Philip Bille Inge Li Gørtz 188

Automated, Deadlock Detection in Synchronized Reentrant Multithreaded Call-Graphs Frank S. de Boer Immo Grabe 200

A Kernel for Convex Recoloring of Weighted Forests Hans L. Bodlaender Marc Comas 212

Symbolic OBDD-Based Reachability Analysis Needs Exponential Space Beate Bollig 224

A Social Vision of Knowledge Representation and Reasoning François Bry Jakub Kotowski 235

Flavors of KWQL, a Keyword Query Language for a Semantic Wiki François Bry Klara Weiand 247

On Pattern Density and Sliding Block Code Behavior for the Besicovitch and Weyl Pseudo-distances Silvio Capobianco 259

On a Labeled Vehicle Routing Problem Hatem Chatti Laurent Gourvès Jérôme Monnot 271

Improved Matrix Interpretation Pierre Courtieu Gladys Gbedo Olivier Pons 283

Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays Maxime Crochemore Costas S. Iliopoulos Marcin Kubica Wojciech Rytter Tomasz Waleń 296

Query Optimization through Cached Queries for Object-Oriented Query Language SBQL Piotr Cybula Kazimierz Subieta 308

Perfect Matching for Biconnected Cubic Graphs in 0(n log² n) Time Krzysztof Diks Piotr Stanczyk 321

Destructive Rule-Based Properties and First-Order Logic David Duris 334

Learning User Preferences for 2CP-Regression for a Recommender System Alan Eckhardt Peter Vojtáš 346

Parallel Randomized Load Balancing: A Lower Bound for a More General Model Guy Even Moti Medina 358

Ant-CSP: An Ant Colony Optimization Algorithm for the Closest String Problem Simone Faro Elisa Pappalardo 370

Linear Complementarity Algorithms for Infinite Games John Fearnley Marcin Jurdziński Rahul Savani 382

Mixing Coverability and Reachability to Analyze VASS with One Zero-Test Alain Finkel Arnaud Sangnier 394

Practically Applicable Formal Methods J&ecedil;drzej Fulara Krzysztof Jakubczyk 407

Fast and Compact Prefix Codes Travis Gagie Gonzalo Navarro Yakov Nekrich 419

New Results on the Complexity of Oriented Colouring on Restricted Digraph Classes Robert Ganian Petr Hliněný 428

Smooth Optimal Decision Strategies for Static Team Optimization Problems and Their Approximations Giorgio Gnecco Marcello Sanguineti 440

Algorithms for the Minimum Edge Cover of H-Subgraphs of a Graph Alexander Grigoriev Bert Marchal Natalya Usotskaya 452

On the Complexity of the Highway Pricing Problem Alexander Grigoriev Joyce van Loon Marc Uetz 465

Accelerating Smart Play-Out David Harel Hillel Kugler Shahar Maoz Itai Segall 477

Optimum Broadcasting in Complete Weighted-Vertex Graphs Hovhannes Harutyunyan Shahin Kamali 489

On Contracting Graphs to Fixed Pattern Graphs Pirn van 't Hof Martin Kamiński Daniël Paulusma Stefan Szeider Diraitrios M. Thilikos 503

Dynamic Edit Distance Table under a General Weighted Cost Function Heikki Hyyrö Kazuyuki Narisawa Shunsuke Inenaga 515

How to Complete an Interactive Configuration Process? Configuring as Shopping Mikoláš Janota Goetz Botterweck Radu Grigore Joao Marques-Silva 528

Design Patterns Instantiation Based on Semantics and Model Transformations Peter Kajsa L'ubomír Majtás 540

A Complete Symbolic Bisimulation for Full Applied Pi Calculus Jia Liu Huimin Lin 552

OTwig: An Optimised Twig Pattern Matching Approach for XML Databases Jun Liu Mark Roantree 564

Picture Recognizability with Automata Based on Wang Tiles Violetta Lonati Matteo Pradella 576

Unilateral Orientation of Mixed Graphs Tamara Mchedlidze Antonios Symvonis 588

Maintaining XML Data Integrity in Programs: An Abstract Datatype Approach Patrick Michel Arnd Poetzsch-Heffter 600

Improving Classification Performance with Focus on the Complex Areas Seyed Zeinolabedin Moussavi Kambiz Zarei Reza Ebrahimpour 612

CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions Friedrich Otto 627

Source Code Rejuvenation Is Not Refactoring Peter Pirkelbauer Damian Dechev Bjarne Stroustrup 639

Empirical Evaluation of Strategies to Detect Logical Change Dependencies Guenter Pirklbauer 651

Efficient Testing of Equivalence of Words in a Free Idempotent Semigroup Jakub Radoszewski Wojciech Rytter 663

An Amortized Search Tree Analysis for k-Leaf Spanning Tree Daniel Raible Henning Fernau 672

Approximate Structural Consistency Michel de Rougemont Adrien Vieilleribiére 685

Comprehensive System for Systematic Case-Driven Software Reuse Micha&lstoke; Śmia&lstoke;ek Audris Kalnins Elina Kalnina Albert Ambroziewicz Tomasz Straszak Katharina Wolter 697

Comparison of Scoring and Order Approach in Description Logic EL(D) Veronika Vaneková Peter Vojtáš 709

Homophily of Neighborhood in Graph Relational Classifier Peter Vojtek Mária Bieliková 721

Multilanguage Debugger Architecture Jan Vraný Michal Píše 731

Student Groups Modeling by Integrating Cluster Representation and Association Rules Mining Danuta Zakrzewska 743

Finding and Certifying Loops Harold Zankl Christian Sternagel Dieter Hofbauer Aart Middeldorp 755

Vertex Ranking with Capacity Ruben van der Zwaan 767

Author Index 779