Reachability Problems
12th International Conference, RP 2018, Marseille, France, September 24-26, 2018, Proceedings
Published on 13. September 2018
XXI, 161 pages
978-3-030-00250-3 (ISBN)
Description
This book constitutes the refereed proceedings of the 12th International Conference on Reachability Problems, RP 2018, held in Marseille, France, in September 2018.
The 11 full papers presented were carefully reviewed and selected from 21 submissions. The papers cover topics such as reachability for infinite state systems; rewriting systems; reachability analysis in counter/timed/cellular/communicating automata; Petri nets; computational aspects of semigroups, groups, and rings; reachability in dynamical and hybrid systems; frontiers between decidable and undecidable reachability problems; complexity and decidability aspects; predictability in iterative maps, and new computational paradigms.
The 11 full papers presented were carefully reviewed and selected from 21 submissions. The papers cover topics such as reachability for infinite state systems; rewriting systems; reachability analysis in counter/timed/cellular/communicating automata; Petri nets; computational aspects of semigroups, groups, and rings; reachability in dynamical and hybrid systems; frontiers between decidable and undecidable reachability problems; complexity and decidability aspects; predictability in iterative maps, and new computational paradigms.
More details
Other editions
Additional editions
Igor Potapov | Pierre-Alain Reynier
Reachability Problems
12th International Conference, RP 2018, Marseille, France, September 24-26, 2018, Proceedings
Book
08/2018
Springer
€53.49
Shipment within 7-9 days
Persons
Content
- Intro
- Preface
- Organization
- Abstracts of Invited Talks
- On the Computational Complexity of Solving Ordinary Differential Equations
- Reachability in Cyber-Physical Systems
- Universal Trees and Quasi-Polynomial Algorithms for Solving Parity Games
- A Counterexample to Thiagarajan's Conjecture on Regular Event Structures
- Safety Verification for Deep Neural Networks with Provable Guarantees (Extended Abstract)
- Contents
- Reachability Analysis of Nonlinear ODEs Using Polytopic Based Validated Runge-Kutta
- 1 Introduction
- 2 Zonotopic Based Validated Runge-Kutta
- 2.1 Initial Value Problem
- 2.2 Validated Runge-Kutta
- 2.3 Affine Arithmetic
- 2.4 Zonotopes
- 2.5 Scheme with Affine Arithmetic
- 2.6 If Integration Fails
- 3 Polytope Geometry
- 3.1 Represent a Polytope Exactly by the Intersection of Zonotopes
- 3.2 Bisect a Polytope
- 4 Nonlinear ODE Reachability of Polytopes
- 4.1 Principle
- 4.2 Examples
- 5 Conclusion
- References
- The Satisfiability of Word Equations: Decidable and Undecidable Theories
- 1 Introduction
- 2 Preliminaries
- 3 Results
- 3.1 Undecidability Results
- 3.2 Quantifier Alternation
- 3.3 Decidability with Restricted Form
- References
- Left-Eigenvectors Are Certificates of the Orbit Problem
- 1 Introduction
- 2 Setting
- 3 Invariants by Generalized Eigenvectors
- 3.1 Certificate Sets of the Rational Orbit Problem
- 3.2 General Existence of a Certificate for the Integer Orbit Problem
- 4 Conclusion and Future Work
- References
- Constrained Dynamic Tree Networks
- 1 Introduction
- 1.1 Related Work
- 2 Alternating Transition System
- 3 Constrained Dynamic Tree Networks
- 3.1 Stability Constraint
- 3.2 Automaton
- 4 Backwards Reachability
- 4.1 The Automaton Ap
- 4.2 From Constraints over P to Constraints over Qp
- 4.3 Closed Set of Constraints
- 4.4 Constructing A'
- 5 Correctness
- 5.1 Soundness
- 5.2 Completeness
- 6 Conclusion
- References
- EXPSPACE-Complete Variant of Countdown Games, and Simulation on Succinct One-Counter Nets
- 1 Introduction
- 2 Basic Definitions
- 3 EXPSPACE-Completeness of Existential Countdown Games
- 4 Reachability Game Reduces to (Bi)simulation Game
- 4.1 Reduction in a General Framework
- 4.2 SOCNRG Reduces to Behavioural Relations on SOCNs
- 5 Additional Remarks
- References
- Revisiting MU-Puzzle. A Case Study in Finite Countermodels Verification
- 1 MIU System and MU Puzzle
- 2 First-Order Logic Encoding and Disproving for MIU
- 2.1 Assumptions on Model Building Procedure
- 2.2 Exact Invariant by Model Building
- 2.3 Variations: Symmetric MIU Problem
- 3 String Rewriting and Regular Invariants
- 4 Conclusion
- References
- Knapsack in Hyperbolic Groups
- 1 Introduction
- 2 General Notations
- 3 Hyperbolic Groups
- 4 Knapsack Problems
- 5 Complexity of Knapsack in Hyperbolic Groups
- 6 Hyperbolic Groups Are Knapsack-Semilinear
- 6.1 Knapsack Expressions of Depth Two
- 6.2 Reduction to Quasi-geodesic Knapsack Expressions
- 6.3 Proof of Theorem7
- 7 More Groups with Knapsack in LogCFL
- 8 Conclusion
- References
- Generalized Tag Systems
- 1 Introduction
- 2 Preliminaries
- 2.1 Generalized Tag Systems
- 2.2 Restrictions of Generalized Tag Systems
- 3 Simulating Generalized Tag Systems in Linear Time
- 4 Relative Prime Tag Systems and the Impossibility of Linear Time Simulation Using Simple Encodings
- References
- Certain Query Answering on Compressed String Patterns: From Streams to Hyperstreams
- 1 Introduction
- 2 Preliminaries
- 3 Compressed String Patterns
- 4 Regular Pattern Inclusion and Matching
- 5 Defining Queries by Automata
- 6 Certain Query Answers and Non-answers
- 7 Certain Query Answering and Non-answering
- 8 Conclusion
- References
- Büchi VASS Recognise 11-complete -languages
- 1 Preliminary Notions
- 2 Hardness for Two Counters
- 3 Representation of IFpre
- 4 Hardness for One Counter
- 5 Inherent Non-determinism
- 6 Concluding Remarks
- References
- Qualitative Reachability for Open Interval Markov Chains
- 1 Introduction
- 2 Open Interval Markov Chains
- 3 Qualitative Reachability: UMC Semantics
- 4 Qualitative Reachability: IMDP Semantics
- 5 Conclusion
- References
- Author Index
