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

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 -