Deciding stability and mortality of piecewise affine dynamical systems

Vincent Blondel (1) , Olivier Bournez (1) , Pascal Koiran (1) , Christos Papadimitriou (1) , John Tsitsiklis (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

We show that several global properties (attractivity, global asymptotic stability and mortality) of discrete time dynamical systems defined by iteration of piecewise-affine maps are undecidable. Such results had been known only for local properties (e.g., point-to-point reachability). These three properties are undecidable in dimension at least two, but turn out to be decidable in one dimension for continuous maps.

Nous montrons que plusieurs propriétés globales (attractivité, stabilité asymptotique globale et mortalité) sont indécidables pour des sytèmes dynamiques à temps discret définis par itération de fonctions affines par morceaux. De tels résultats n'étaient connus auparavant que pour des propriétés locales (comme par exemple l'atteignabilité point à point). Les trois propriétés ci-dessus sont indécidables en dimension au moins égale à deux, mais se trouvent être décidables en dimension un pour des fonctions continues.

Mots clés: Stability; Mortality; Piecewise Affine Systems; Piecewise Linear Systems; Hybrid Systems; Dynamical Systems; Decidability

Mots clés: Sytèmes Dynamiques; Systèmes Affines par Morceaux; Systèmes Hybrides; Systèmes Linéaires par Morceaux; Décidabilité; Mortalité; Stabilité

Domaines: Informatique [cs]

Vincent Blondel, Olivier Bournez, Pascal Koiran, Christos Papadimitriou, John Tsitsiklis. Deciding stability and mortality of piecewise affine dynamical systems. [Research Report] LIP RR-1999-05, Laboratoire de l'informatique du parallélisme. 1999, 2+11p. ⟨hal-02101802⟩