Reachability problems : 3rd international workshop, RP 2009, Palaiseau, France, September 23-25, 2009 : proceedings

This book constitutes the research papers presented at the 3rd International Workshop, RP 2009 held in Palaiseau, France, September 23-25, 2009. The 20 full papers of this workshop reflect reachability problems that appear in algebraic structures, computational models, hybrid systems and verification. Reachability is a fundamental problem in the context of many models and abstractions which are describing various computational processes. Topics of interest include reachability problems in infinite state systems, rewriting systems, dynamical and hybrid systems, reachability problems in logic and verification, reachability analysis in different computational models, counter, timed, cellular, communicating automata, Petri-Nets, computational aspects of algebraic structures and predictability in iterative maps and new computational paradigms. Front Matter....Pages - On the Reachability Problem for Dynamic Networks of Concurrent Pushdown Systems....Pages 1-2 Formalisms for Specifying Markovian Population Models....Pages 3-23 Reachability for Continuous and Hybrid Systems....Pages 24-25 Algorithmic Information Theory and Foundations of Probability....Pages 26-34 Model Checking as A Reachability Problem....Pages 35-35 Automatic Verification of Directory-Based Consistency Protocols....Pages 36-50 On Yen’s Path Logic for Petri Nets....Pages 51-63 Probabilistic Model Checking of Biological Systems with Uncertain Kinetic Rates....Pages 64-78 How to Tackle Integer Weighted Automata Positivity....Pages 79-92 A Reduction Theorem for the Verification of Round-Based Distributed Algorithms....Pages 93-106 Computable CTL * for Discrete-Time and Continuous-Space Dynamic Systems....Pages 107-119 An Undecidable Permutation of the Natural Numbers....Pages 120-126 Forward Analysis of Dynamic Network of Pushdown Systems Is Easier without Order....Pages 127-140 Counting Multiplicity over Infinite Alphabets....Pages 141-153 The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane....Pages 154-165 Games with Opacity Condition....Pages 166-175 Abstract Counterexamples for Non-disjunctive Abstractions....Pages 176-188 Cross-Checking - Enhanced Over-Approximation of the Reachable Global State Space of Component-Based Systems....Pages 189-202 Games on Higher Order Multi-stack Pushdown Systems....Pages 203-216 Limit Set Reachability in Asynchronous Graph Dynamical Systems....Pages 217-232 Back Matter....Pages -