Reachability Problems

1. Front Matter

   PDF

2. On the Reachability Problem for Dynamic Networks of Concurrent Pushdown Systems

   • Mohamed Faouzi Atig, Ahmed Bouajjani

   Pages 1-2

3. Formalisms for Specifying Markovian Population Models

   • Thomas A. Henzinger, Barbara Jobstmann, Verena Wolf

   Pages 3-23

4. Reachability for Continuous and Hybrid Systems

   • Oded Maler

   Pages 24-25

5. Algorithmic Information Theory and Foundations of Probability

   • Alexander Shen

   Pages 26-34

6. Model Checking as A Reachability Problem

   • Moshe Y. Vardi

   Pages 35-35

7. Automatic Verification of Directory-Based Consistency Protocols

   • Parosh Aziz Abdulla, Giorgio Delzanno, Ahmed Rezine

   Pages 36-50

8. On Yen’s Path Logic for Petri Nets

   • Mohamed Faouzi Atig, Peter Habermehl

   Pages 51-63

9. Probabilistic Model Checking of Biological Systems with Uncertain Kinetic Rates

   • Roberto Barbuti, Francesca Levi, Paolo Milazzo, Guido Scatena

   Pages 64-78

10. How to Tackle Integer Weighted Automata Positivity

    • Yohan Boichut, Pierre-Cyrille Héam, Olga Kouchnarenko

    Pages 79-92

11. A Reduction Theorem for the Verification of Round-Based Distributed Algorithms

    • Mouna Chaouch-Saad, Bernadette Charron-Bost, Stephan Merz

    Pages 93-106

12. Computable CTL ^* for Discrete-Time and Continuous-Space Dynamic Systems

    • Pieter Collins, Ivan S. Zapreev

    Pages 107-119

13. An Undecidable Permutation of the Natural Numbers

    • Eero Lehtonen

    Pages 120-126

14. Forward Analysis of Dynamic Network of Pushdown Systems Is Easier without Order

    • Denis Lugiez

    Pages 127-140

15. Counting Multiplicity over Infinite Alphabets

    • Amaldev Manuel, R. Ramanujam

    Pages 141-153

16. The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane

    • Maurice Margenstern

    Pages 154-165

17. Games with Opacity Condition

    • Bastien Maubert, Sophie Pinchinat

    Pages 166-175

18. Abstract Counterexamples for Non-disjunctive Abstractions

    • Kenneth L. McMillan, Lenore D. Zuck

    Pages 176-188

19. Cross-Checking - Enhanced Over-Approximation of the Reachable Global State Space of Component-Based Systems

    • Mila Majster-Cederbaum, Christoph Minnameier

    Pages 189-202

20. Games on Higher Order Multi-stack Pushdown Systems

    • Anil Seth

    Pages 203-216

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.

• Permutation
• algebraic structures
• algorithms
• automata
• calculus
• computational models
• hyprid systems
• infinite state systems
• information theory
• logic
• petri nets
• reachability problems
• rewriting systems
• verification
• algorithm analysis and problem complexity

• Ecole Polytechnique, Laboratoire d’ Informatique (LIX), Palaiseau Cedex, France

  Olivier Bournez

• Department of Computer Science, Ashton Building, University of Liverpool, Liverpool, England

  Igor Potapov

Policies and ethics