Reachability Problems

1. Front Matter

   PDF

2. Complexity Bounds for Ordinal-Based Termination

   • Sylvain Schmitz

   Pages 1-19

3. On The Complexity of Bounded Time Reachability for Piecewise Affine Systems

   • Hugo Bazille, Olivier Bournez, Walid Gomaa, Amaury Pouly

   Pages 20-31

4. Reachability and Mortality Problems for Restricted Hierarchical Piecewise Constant Derivatives

   • Paul C. Bell, Shang Chen, Lisa Jackson

   Pages 32-44

5. Parameterized Verification of Communicating Automata under Context Bounds

   • Benedikt Bollig, Paul Gastin, Jana Schubert

   Pages 45-57

6. Regular Strategies in Pushdown Reachability Games

   • A. Carayol, M. Hague

   Pages 58-71

7. Parameterized Verification of Graph Transformation Systems with Whole Neighbourhood Operations

   • Giorgio Delzanno, Jan Stückrath

   Pages 72-84

8. Equivalence Between Model-Checking Flat Counter Systems and Presburger Arithmetic

   • Stéphane Demri, Amit Kumar Dhar, Arnaud Sangnier

   Pages 85-97

9. Synthesising Succinct Strategies in Safety and Reachability Games

   • Gilles Geeraerts, Joël Goossens, Amélie Stainer

   Pages 98-111

10. Integer Vector Addition Systems with States

    • Christoph Haase, Simon Halfon

    Pages 112-124

11. Reachability in MDPs: Refining Convergence of Value Iteration

    • Serge Haddad, Benjamin Monmege

    Pages 125-137

12. On the Expressiveness of Metric Temporal Logic over Bounded Timed Words

    • Hsi-Ming Ho

    Pages 138-150

13. Trace Inclusion for One-Counter Nets Revisited

    • Piotr Hofman, Patrick Totzke

    Pages 151-162

14. Mean-Payoff Games with Partial-Observation

    • Paul Hunter, Guillermo A. Pérez, Jean-François Raskin

    Pages 163-175

15. Parameter Synthesis for Probabilistic Timed Automata Using Stochastic Game Abstractions

    • Aleksandra Jovanović, Marta Kwiatkowska

    Pages 176-189

16. On Functions Weakly Computable by Petri Nets and Vector Addition Systems

    • J. Leroux, Ph. Schnoebelen

    Pages 190-202

17. Generalized Craig Interpolation for Stochastic Satisfiability Modulo Theory Problems

    • Ahmed Mahdi, Martin Fränzle

    Pages 203-215

18. Transformations for Compositional Verification of Assumption-Commitment Properties

    • Ahmed Mahdi, Bernd Westphal, Martin Fränzle

    Pages 216-229

19. Compositional Reachability in Petri Nets

    • Julian Rathke, Paweł Sobociński, Owen Stephens

    Pages 230-243

20. Back Matter

    PDF

This book constitutes the proceedings of the 8th International Workshop on Reachability Problems, RP 2014, held in Oxford, UK, in September 2014. The 17 papers presented in this volume were carefully reviewed and selected from 25 submissions. The book also contains a paper summarizing the invited talk. The papers offer new approaches for the modelling and analysis of computational processes by combining mathematical, algorithmic, and computational techniques.

• Petri nets
• automata theory
• communicating automata
• computational aspects of semigroups, groups, and rings
• computational complexity
• decidable and undecidable reachability problems
• dynamical and hybrid systems
• formal languages
• formal methods
• infinite state systems
• prdictability in iterative maps
• program analysis
• reachability analysis
• rewrite systems
• rewriting systems
• software system models
• theory of computation
• timed automata

• Department of Computer Science, University of Oxford, Oxford, UK

  Joël Ouaknine

• Department of Computer Science, University of Liverpool, Liverpool, UK

  Igor Potapov

• Department of Computer Science, University of Oxford, UK

  James Worrell

Policies and ethics