The stability of saturated linear dynamical systems is undecidable

DOI10.1006/jcss.2000.1737zbMath0995.03033OpenAlexW2017888836MaRDI QIDQ5943100

Blondel, Vincent D., John N. Tsitsiklis, Olivier Bournez, Pascal Koiran

Publication date: 15 October 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2000.1737

zbMATH Keywords

global asymptotic stabilityTuring machinediscrete dynamical systemsaturated linear system

Mathematics Subject Classification ID

Asymptotic stability in control theory (93D20) Undecidability and degrees of sets of sentences (03D35) Turing machines and related notions (03D10)

Related Items

On The Complexity of Bounded Time Reachability for Piecewise Affine Systems, Reachability Problems for One-Dimensional Piecewise Affine Maps, Computability and Dynamical Systems, On the complexity of bounded time and precision reachability for piecewise affine systems, Exponential asymptotic optimality of Whittle index policy, Deciding the point-to-fixed-point problem for skew tent maps on an interval, On the geometry and regularity of invariant sets of piecewise-affine automorphisms on the Euclidean space, Optimal and robust controller synthesis using energy timed automata with uncertainty, A survey of computational complexity results in systems and control, Computability in planar dynamical systems, Turing Machines Can Be Efficiently Simulated by the General Purpose Analog Computer, On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases, Transiently chaotic neural networks with piecewise linear output functions, Computability, noncomputability, and hyperbolic systems, Unnamed Item, Optimal and robust controller synthesis. Using energy timed automata with uncertainty, Topological formulation of termination properties of iterates of functions, On the presence of periodic configurations in Turing machines and in counter machines.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The algorithmic analysis of hybrid systems
• What's decidable about hybrid automata?
• Complexity of stability and controllability of elementary hybrid systems
• Analog computation via neural networks
• Computability with low-dimensional dynamical systems
• On the computational power of dynamical systems and hybrid systems
• Reachability analysis of dynamical systems having piecewise-constant derivatives
• On the computational power of neural nets
• Overview of complexity and decidability results for three classes of elementary nonlinear systems
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Generalized shifts: unpredictability and undecidability in dynamical systems
• The undecidability of the Turing machine immortality problem
• A survey of computational complexity results in systems and control
• Deciding stability and mortality of piecewise affine dynamical systems