zbMATH — the first resource for mathematics

Deciding stability and mortality of piecewise affine dynamical systems. (English) Zbl 0973.68067
Summary: In this paper we study problems such as: given a discrete time dynamical system of the form \(x(t+1)=f (x(t))\) where \(f: R^{n}\rightarrow R^{n}\) is a piecewise affine function, decide whether all trajectories converge to 0. We show in our main theorem that this attractivity problem is undecidable as soon as \(n\geqslant 2\). The same is true of two related problems: Stability (is the dynamical system globally asymptotically stable?) and mortality (do all trajectories go through 0?). We then show that attractivity and stability become decidable in dimension 1 for continuous functions.

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI
[1] Alur, R.; Courcoubetis, C.; Halbwachs, N.; Henzinger, T.A.; Ho, P.-H.; Nicollin, X.; Olivero, A.; Sifakis, J.; Yovine, S., The algorithmic analysis of hybrid systems, Theoret. comput. sci., 138, 3-34, (1995) · Zbl 0874.68206
[2] Asarin, A.; Maler, O.; Pnueli, A., Reachability analysis of dynamical systems having piecewise constant derivatives, Theoret. comput. sci., 138, 35-66, (1995) · Zbl 0884.68050
[3] V.D. Blondel, O. Bournez, P. Koiran, J.N. Tsitsiklis, The stability of saturated linear dynamical systems is undecidable, in: H. Reichel, S. Tison (Eds.), Proceedings of STACS 2000, Lecture Notes in Computer Science 1770, Springer Verlag, 2000, pp. 479-490. · Zbl 0963.93070
[4] Blondel, V.D.; Tsitsiklis, J.N., Complexity of stability and controllability of elementary hybrid systems, Automatica, 35, 3, 479-489, (1999) · Zbl 0943.93044
[5] Blondel, V.D.; Tsitsiklis, J.N., A survey of computational complexity results in systems and control, automatica, 36, 1249-1274, (2000) · Zbl 0989.93006
[6] Bournez, O.; Cosnard, M., On the computational power of dynamical systems and hybrid systems, Theoret. comput. sci., 168, 417-459, (1996) · Zbl 0874.68303
[7] T. Henzinger, P. Kopke, A. Puri, P. Varaiya, What’s decidable about hybrid automata, Proc. 27th ACM Symp. on the Theory of Computing, 1995. · Zbl 0978.68534
[8] Hooper, P., The undecidability of the Turing machine immortality problem, J. symbolic logic, 2, 219-234, (1966) · Zbl 0173.01201
[9] Hopcroft, J.E.; Ullman, J.D., Formal languages and their relation to automata, (1969), Addison-Wesley Reading, MA · Zbl 0196.01701
[10] H. Hyotyniemu, On unsolvability of nonlinear system stability, Proc. ECC Conf., Brussels (CD-Rom), 1997.
[11] Koiran, P.; Cosnard, M.; Garzon, M., Computability properties of low-dimensional dynamical systems, Theoret. comput. sci., 132, 113-128, (1994) · Zbl 0821.68053
[12] Koiran, P., A family of universal recurrent networks, Theoret. comput. sci., 168, 473-480, (1996) · Zbl 0874.68250
[13] Moore, C., Unpredictability and undecidability in dynamical systems, Phys. rev. lett., 64, 20, 2354-2357, (1990) · Zbl 1050.37510
[14] Siegelmann, H.; Sontag, E., On the computational power of neural nets, J. comput. system sci., 50, 132-150, (1995) · Zbl 0826.68104
[15] Sontag, E., Mathematical control theory, (1990), Springer New York
[16] E. Sontag, From linear to nonlinear: some complexity comparisons, Proc. IEEE Conf. Decision and Control, New Orleans, 1995, pp. 2916-2920.
[17] Sontag, E., Interconnected automata and linear systemsa theoretical framework in discrete time, (), 436-448
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.