The stability of saturated linear dynamical systems is undecidable
From MaRDI portal
This paper is devoted to the study of the following problem: given a discrete-time dynamical system of the form \(x_{t+1}= f(x_t)\), where \(f:\mathbb{R}^n\to \mathbb{R}^n\) is a saturated linear function or, more generally, a continuous piecewise affine function, decide whether all trajectories converge to the origin. The authors prove that the global asymptotic stability of a saturated linear system is not decidable.
Recommendations
Cites work
- A survey of computational complexity results in systems and control
- Analog computation via neural networks
- Complexity of stability and controllability of elementary hybrid systems
- Computability with low-dimensional dynamical systems
- Deciding stability and mortality of piecewise affine dynamical systems
- Energy functions in neural networks with continuous local functions
- Generalized shifts: unpredictability and undecidability in dynamical systems
- scientific article; zbMATH DE number 3827680 (Why is no real title available?)
- scientific article; zbMATH DE number 4029737 (Why is no real title available?)
- scientific article; zbMATH DE number 45943 (Why is no real title available?)
- scientific article; zbMATH DE number 1182386 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On the computational power of dynamical systems and hybrid systems
- On the computational power of neural nets
- Overview of complexity and decidability results for three classes of elementary nonlinear systems
- Reachability analysis of dynamical systems having piecewise-constant derivatives
- The algorithmic analysis of hybrid systems
- The undecidability of the Turing machine immortality problem
- What's decidable about hybrid automata?
Cited in
(24)- Topological formulation of termination properties of iterates of functions
- Computability in planar dynamical systems
- On the presence of periodic configurations in Turing machines and in counter machines.
- Optimal and robust controller synthesis using energy timed automata with uncertainty
- Computability, noncomputability, and hyperbolic systems
- Optimal and robust controller synthesis. Using energy timed automata with uncertainty
- Deciding the point-to-fixed-point problem for skew tent maps on an interval
- On the complexity of bounded time and precision reachability for piecewise affine systems
- Computability and dynamical systems
- Reachability problems for one-dimensional piecewise affine maps
- On the geometry and regularity of invariant sets of piecewise-affine automorphisms on the Euclidean space
- On the complexity of bounded time reachability for piecewise affine systems
- scientific article; zbMATH DE number 1500537 (Why is no real title available?)
- Turing machines can be efficiently simulated by the general purpose analog computer
- scientific article; zbMATH DE number 7559393 (Why is no real title available?)
- On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases
- A survey of computational complexity results in systems and control
- Deciding stability and mortality of piecewise affine dynamical systems
- Exponential asymptotic optimality of Whittle index policy
- Undecidability in physics: a review
- A dynamical system which must be stable whose stability cannot be proved
- Transiently chaotic neural networks with piecewise linear output functions
- A universal uniform approximation theorem for neural networks
- The domino problem is decidable for robust tilesets
This page was built for publication: The stability of saturated linear dynamical systems is undecidable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5943100)
