Amazon cover image
Image from Amazon.com

Reachability problems : 12th International Conference, RP 2018, Marseille, France, September 24-26, 2018, Proceedings / Igor Potapov, Pierre-Alain Reynier (eds.).

By: Contributor(s): Material type: TextTextSeries: Lecture notes in computer science ; 11123. | LNCS sublibrary. SL 1, Theoretical computer science and general issues.Publisher: Cham, Switzerland : Springer, 2018Description: 1 online resource (xxi, 161 pages) : illustrationsContent type:
  • text
Media type:
  • computer
Carrier type:
  • online resource
ISBN:
  • 9783030002503
  • 3030002500
  • 3030002497
  • 9783030002497
  • 9783030002510
  • 3030002519
Other title:
  • RP 2018
Subject(s): Genre/Form: Additional physical formats: Printed edition:: No title; Printed edition:: No titleDDC classification:
  • 004 23
LOC classification:
  • QA76.76.V47
Online resources:
Contents:
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
Summary: 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.
Holdings
Item type Current library Collection Call number Status Date due Barcode Item holds
eBook eBook e-Library eBook LNCS Available
Total holds: 0

International conference proceedings.

Includes bibliographical references and author index.

Online resource; title from PDF title page (SpringerLink, viewed September 19, 2018).

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.

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

Powered by Koha