On the complexity of bounded time reachability for piecewise affine systems

DOI10.1007/978-3-319-11439-2_2MaRDI QIDQ3447692zbMATH OpenOpenAlexFDO

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

Publication date 28 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-11439-2_2

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the complexity of bounded time and precision reachability for piecewise affine systems
• Reachability analysis of dynamical systems having piecewise-constant derivatives
• Deciding stability and mortality of piecewise affine dynamical systems
• On reachability problem in 1-dimensional 2-interval piecewise-affine mappings
• Reachability problems for hierarchical piecewise constant derivative systems

Cites work

• Computability with low-dimensional dynamical systems
• Computing over the reals with addition and order
• Generalized shifts: unpredictability and undecidability in dynamical systems
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1927563 (Why is no real title available?)
• scientific article; zbMATH DE number 1794363 (Why is no real title available?)
• Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract)
• On the computational power of neural nets
• Reachability analysis of dynamical systems having piecewise-constant derivatives
• Reachability problems for hierarchical piecewise constant derivative systems
• The stability of saturated linear dynamical systems is undecidable
• What's decidable about hybrid automata?

Cited in

(10)

• The complexity of some reachability problems for a system on a finite group
• Reachability analysis of dynamical systems having piecewise-constant derivatives
• Formal analysis of piecewise affine systems through formula-guided refinement
• On the complexity of bounded time and precision reachability for piecewise affine systems
• Reachability problems for one-dimensional piecewise affine maps
• The Complexity of Bounded Synthesis for Timed Control with Partial Observability
• On reachability problem in 1-dimensional 2-interval piecewise-affine mappings
• On the decidability of reachability in linear time-invariant systems
• Mortality and Edge-to-Edge Reachability are Decidable on Surfaces
• Reachability and mortality for two-dimensional RHPCD systems are co-NP-hard

This page was built for publication: On the complexity of bounded time reachability for piecewise affine systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3447692)