Reachability analysis of dynamical systems having piecewise-constant derivatives

DOI10.1016/0304-3975(94)00228-BzbMath0884.68050MaRDI QIDQ1367528

Amir Pnueli, Eugene Asarin, Oded Maler

Publication date: 29 September 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

dynamical systemsreachabilityPCD systemspiecewise-constant derivatives

Mathematics Subject Classification ID

Controllability (93B05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (65)

On The Complexity of Bounded Time Reachability for Piecewise Affine Systems ⋮ Algorithmic analysis of polygonal hybrid systems. I: Reachability ⋮ Verification of Hybrid Systems ⋮ Reachability Problems for One-Dimensional Piecewise Affine Maps ⋮ On the computational power of dynamical systems and hybrid systems ⋮ Computability and Dynamical Systems ⋮ On the complexity of bounded time and precision reachability for piecewise affine systems ⋮ Complexity of reachability problems for finite discrete dynamical systems ⋮ On the decidability and complexity of problems for restricted hierarchical hybrid systems ⋮ Computation with perturbed dynamical systems ⋮ Hybridization methods for the analysis of nonlinear systems ⋮ Some bounds on the computational power of piecewise constant derivative systems (extended abstract) ⋮ Polynomial interrupt timed automata: verification and expressiveness ⋮ An RNA-based theory of natural universal computation ⋮ Timed-Automata Abstraction of Switched Dynamical Systems Using Control Funnels ⋮ Deciding Concurrent Planar Monotonic Linear Hybrid Systems ⋮ The Transitivity Problem of Turing Machines ⋮ Approximating Continuous Systems by Timed Automata ⋮ Reachability in Linear Dynamical Systems ⋮ Updatable Timed Automata with Additive and Diagonal Constraints ⋮ Supervisory control and reactive synthesis: a comparative introduction ⋮ Low dimensional hybrid systems -- decidable, undecidable, don't know ⋮ PuRSUE -- from specification of robotic environments to synthesis of controllers ⋮ Timed-automata abstraction of switched dynamical systems using control invariants ⋮ On the decidability of reachability in continuous time linear time-invariant systems ⋮ STORMED Hybrid Systems ⋮ Reachability of Uncertain Nonlinear Systems Using a Nonlinear Hybridization ⋮ Tight space-noise tradeoffs in computing the ergodic measure ⋮ REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS ⋮ Unnamed Item ⋮ Interrupt timed automata: verification and expressiveness ⋮ Modelling hybrid production systems through the ACD specification: a case study in the fibre-glass industry ⋮ Computing Omega-Limit Sets in Linear Dynamical Systems ⋮ Cyclic linear differential automata: A simple class of hybrid dynamical systems ⋮ Timed discrete event control of parallel production lines with continuous outputs ⋮ Perfect simulation of a class of stochastic hybrid systems with an application to peer to peer systems ⋮ CONTINUOUS PETRI NETS: EXPRESSIVE POWER AND DECIDABILITY ISSUES ⋮ Computation in gene networks ⋮ A survey of computational complexity results in systems and control ⋮ Boundedness of the Domain of Definition is Undecidable for Polynomial ODEs ⋮ A decidable class of planar linear hybrid systems ⋮ A survey of challenges for runtime verification from advanced application domains (beyond software) ⋮ Achilles and the tortoise climbing up the arithmetical hierarchy ⋮ Computing reachable sets for uncertain nonlinear hybrid systems using interval constraint-propagation techniques ⋮ Deciding stability and mortality of piecewise affine dynamical systems ⋮ The stability of saturated linear dynamical systems is undecidable ⋮ How much can analog and hybrid systems be proved (super-)Turing ⋮ Span-reachability and observability of bilinear hybrid systems ⋮ Computing reachable sets for uncertain nonlinear monotone systems ⋮ Discrete-time hybrid modeling and verification of the batch evaporator process benchmark ⋮ Interrupt Timed Automata ⋮ Reachability analysis of rational eigenvalue linear systems ⋮ Computable analysis with applications to dynamic systems ⋮ Achilles and the tortoise climbing up the hyper-arithmetical hierarchy ⋮ Closed-form analytic maps in one and two dimensions can simulate universal Turing machines ⋮ Regularizability of complex switched server queueing networks modelled as hybrid dynamical systems ⋮ What is a universal computing machine? ⋮ Computational bounds on polynomial differential equations ⋮ Continuity and computability of reachable sets ⋮ Decidable integration graphs. ⋮ A theory of complexity for continuous time systems ⋮ Some decidable results on reachability of solvable systems ⋮ A Survey on Analog Models of Computation ⋮ Limit cycle analysis of a class of hybrid gene regulatory networks ⋮ A supervisory control method for ensuring the conformance of real-time discrete event systems

Cites Work

• Universal computation and other capabilities of hybrid and continuous dynamical systems
• Model-checking in dense real-time
• A theory of timed automata
• Symbolic model checking for real-time systems
• Computability and complexity of ray tracing
• On some relations between dynamical systems and transition systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Reachability analysis of dynamical systems having piecewise-constant derivatives