Deciding stability and mortality of piecewise affine dynamical systems

Vincent D. Blondel; Olivier Bournez; Pascal Koiran; Christos H. Papadimitriou; John N. Tsitsiklis

doi:10.1016/S0304-3975(00)00399-6

Deciding stability and mortality of piecewise affine dynamical systems

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

University of Louvain
LORIA Laboratoire Lorrain de Recherche en Informatique et ses Applications
Ecole Normale Supérieure de Lyon
University of California, Berkeley
Massachusetts Institute of Technology

Research output: Contribution to journal › Article › peer-review

Abstract

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ⁿ → Rⁿ 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≥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.

Original language	English
Pages (from-to)	687-696
Number of pages	10
Journal	Theoretical Computer Science
Volume	255
Issue number	1-2
DOIs	https://doi.org/10.1016/S0304-3975(00)00399-6
Publication status	Published - 7 Aug 2001
Externally published	Yes

Keywords

Decidability
Discrete dynamical systems
Hybrid systems
Mortality
Piecewise affine systems
Piecewise linear systems
Stability

Access to Document

10.1016/S0304-3975(00)00399-6

Cite this

@article{de0b325848d84ad4979ed35c5f11b10d,

title = "Deciding stability and mortality of piecewise affine dynamical systems",

abstract = "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:Rn → Rn 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≥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.",

keywords = "Decidability, Discrete dynamical systems, Hybrid systems, Mortality, Piecewise affine systems, Piecewise linear systems, Stability",

author = "Blondel, \{Vincent D.\} and Olivier Bournez and Pascal Koiran and Papadimitriou, \{Christos H.\} and Tsitsiklis, \{John N.\}",

year = "2001",

month = aug,

day = "7",

doi = "10.1016/S0304-3975(00)00399-6",

language = "English",

volume = "255",

pages = "687--696",

journal = "Theoretical Computer Science",

issn = "0304-3975",

number = "1-2",

}

TY - JOUR

T1 - Deciding stability and mortality of piecewise affine dynamical systems

AU - Blondel, Vincent D.

AU - Bournez, Olivier

AU - Koiran, Pascal

AU - Papadimitriou, Christos H.

AU - Tsitsiklis, John N.

PY - 2001/8/7

Y1 - 2001/8/7

N2 - 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:Rn → Rn 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≥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.

AB - 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:Rn → Rn 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≥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.

KW - Decidability

KW - Discrete dynamical systems

KW - Hybrid systems

KW - Mortality

KW - Piecewise affine systems

KW - Piecewise linear systems

KW - Stability

U2 - 10.1016/S0304-3975(00)00399-6

DO - 10.1016/S0304-3975(00)00399-6

M3 - Article

AN - SCOPUS:0034915180

SN - 0304-3975

VL - 255

SP - 687

EP - 696

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

Deciding stability and mortality of piecewise affine dynamical systems

Abstract

Keywords

Access to Document

Fingerprint

Cite this