SOFSEM 2009: Theory and Practice of Computer Science: 35th Conference on Current Trends in Theory and Practice of Computer Science, à pindlerův Mlýn, Czech Republic, January 24-30, 2009. Proceedings

This book constitutes the refereed proceedings of the 35th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2009, held in � pindleruv Mlýn, Czech Republic, in January 2009. The 49 revised full papers, presented together with 9 invited contributions, were carefully reviewed and selected from 132 submissions. SOFSEM 2009 was organized around the following four tracks: Foundations of Computer Science; Theory and Practice of Software Services; Game Theoretic Aspects of E-commerce; and Techniques and Tools for Formal Verification. Content: Front Matter....Pages - A New Analysis of Expected Revenue....Pages 1-2 Can Component/Service-Based Systems Be Proved Correct?....Pages 3-18 Probabilistic Acceptors for Languages over Infinite Words....Pages 19-33 Automatic Verification of Heap Manipulation Using Separation Logic....Pages 34-34 Technology Diffusion in Social Networks....Pages 35-36 Service Oriented Architecture Pitfalls....Pages 37-45 Algorithms for Solving Infinite Games....Pages 46-48 Randomness and Determination, from Physics and Computing towards Biology....Pages 49-61 When Analysis Fails: Heuristic Mechanism Design via Self-correcting Procedures....Pages 62-66 On Compositionality, Efficiency, and Applicability of Abstraction in Probabilistic Systems....Pages 67-78 Framed Versus Unframed Two-Dimensional Languages....Pages 79-92 Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes....Pages 93-104 The Shortcut Problem – Complexity and Approximation....Pages 105-116 Green Computing: Energy Consumption Optimized Service Hosting....Pages 117-128 On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem....Pages 129-140 Natural Specifications Yield Decidability for Distributed Synthesis of Asynchronous Systems....Pages 141-152 Epistemic Strategies and Games on Concurrent Processes....Pages 153-166 On Finite Bases for Weak Semantics: Failures Versus Impossible Futures....Pages 167-180 On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay....Pages 181-192 Time and Fairness in a Process Algebra with Non-blocking Reading....Pages 193-204 Expressiveness of Multiple Heads in CHR....Pages 205-216 Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes....Pages 217-228 A Framework for Mutant Genetic Generation for WS-BPEL....Pages 229-240 Implementing Services by Partial State Machines....Pages 241-254 Pattern Matching with Swaps for Short Patterns in Linear Time....Pages 255-266 Automatic Bug Detection in Microcontroller Software by Static Program Analysis....Pages 267-278 On the Unification of Process Semantics: Observational Semantics....Pages 279-290 Factoring and Testing Primes in Small Space....Pages 291-302 Adaptive Incentive-Compatible Sponsored Search Auction....Pages 303-316 Semantically-Aided Data-Aware Service Workflow Composition....Pages 317-328 Increasing Machine Speed in On-Line Scheduling of Weighted Unit-Length Jobs in Slotted Time....Pages 329-340 Abstract Storage Devices....Pages 341-352 On Stateless Deterministic Restarting Automata....Pages 353-364 User Care Preference-Based Semantic Service Discovery in a Ubiquitous Environment....Pages 365-375 Safe Reasoning with Logic LTS....Pages 376-387 Partial Order Semantics of Types of Nets....Pages 388-400 A Problem Kernelization for Graph Packing....Pages 401-412 Conjunctive Grammars with Restricted Disjunction ....Pages 413-424 Modelling and Verifying Mobile Systems Using π-Graphs....Pages 425-436 On Some SAT-Variants over Linear Formulas....Pages 437-448 The Simple Reachability Problem in Switch Graphs....Pages 449-460 Unambiguous Erasing Morphisms in Free Monoids....Pages 461-472 An Efficient Symbolic Elimination Algorithm for the Stochastic Process Algebra Tool CASPA....Pages 473-484 Asynchronous Deterministic Rendezvous on the Line....Pages 485-496 Design Validation by Symbolic Simulation and Equivalence Checking: A Case Study in Memory Optimization for Image Manipulation....Pages 497-508 Group Input Machine....Pages 509-520 From Outermost Termination to Innermost Termination....Pages 521-532 Improved Algorithms for the 2-Vertex Disjoint Paths Problem....Pages 533-545 Event-Clock Visibly Pushdown Automata....Pages 546-557 A Machine Checked Soundness Proof for an Intermediate Verification Language....Pages 558-569 Symbolic State-Space Generation of Asynchronous Systems Using Extensible Decision Diagrams....Pages 570-581 Symbolic Reachability Analysis of Integer Timed Petri Nets....Pages 582-594 On Toda’s Theorem in Structural Communication Complexity....Pages 595-608 The Minimum Reload s-t Path/Trail/Walk Problems....Pages 609-620 Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression....Pages 621-632 A New Family of Regular Operators Fitting with the Position Automaton Computation....Pages 633-644 A Formal Model of Business Application Integration from Web Services (Position Paper)....Pages 645-655 Back Matter....Pages 656-667 ....Pages - This book constitutes the refereed proceedings of the 35th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2009, held in Špindleruv Mlýn, Czech Republic, in January 2009. The 49 revised full papers, presented together with 9 invited contributions, were carefully reviewed and selected from 132 submissions. SOFSEM 2009 was organized around the following four tracks: Foundations of Computer Science; Theory and Practice of Software Services; Game Theoretic Aspects of E-commerce; and Techniques and Tools for Formal Verification