SOFSEM 2009: Theory and Practice of Computer Science

Invited Talks.- A New Analysis of Expected Revenue.- Can Component/Service-Based Systems Be Proved Correct?.- Probabilistic Acceptors for Languages over Infinite Words.- Automatic Verification of Heap Manipulation Using Separation Logic.- Technology Diffusion in Social Networks.- Service Oriented Architecture Pitfalls.- Algorithms for Solving Infinite Games.- Randomness and Determination, from Physics and Computing towards Biology.- When Analysis Fails: Heuristic Mechanism Design via Self-correcting Procedures.- Regular Papers.- On Compositionality, Efficiency, and Applicability of Abstraction in Probabilistic Systems.- Framed Versus Unframed Two-Dimensional Languages.- Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes.- The Shortcut Problem - Complexity and Approximation.- Green Computing: Energy Consumption Optimized Service Hosting.- On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem.- Natural Specifications Yield Decidability for Distributed Synthesis of Asynchronous Systems.- Epistemic Strategies and Games on Concurrent Processes.- On Finite Bases for Weak Semantics: Failures Versus Impossible Futures.- On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay.- Time and Fairness in a Process Algebra with Non-blocking Reading.- Expressiveness of Multiple Heads in CHR.- Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes.- A Framework for Mutant Genetic Generation for WS-BPEL.- Implementing Services by Partial State Machines.- Pattern Matching with Swaps for Short Patterns in Linear Time.- Automatic Bug Detection in Microcontroller Software by Static Program Analysis.- On the Unification of Process Semantics: Observational Semantics.- Factoring andTesting Primes in Small Space.- Adaptive Incentive-Compatible Sponsored Search Auction.- Semantically-Aided Data-Aware Service Workflow Composition.- Increasing Machine Speed in On-Line Scheduling of