Deciding stability and mortality of piecewise affine dynamical systems

Blondel, Vincent;Bournez, O;Koiran, P;Papadimitriou, CH;Tsitsiklis, John
(2001) Theoretical Computer Science — Vol. 255, n° 1-2, p. 687-696 (2001)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 116.37 KB
Request a copy

Details

Authors
  • Blondel, Vincentorcid-logoUCLouvain
    Author
  • Bournez, O
    Author
  • Koiran, P
    Author
  • Papadimitriou, CH
    Author
  • Tsitsiklis, John
    Author
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-n --> 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 greater than or equal to2. 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 AM-activity and Stability become decidable in dimension 1 for continuous functions. (C) 2001 Elsevier Science B.V. All rights reserved.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Blondel, V., Bournez, O., Koiran, P., Papadimitriou, C., & Tsitsiklis, J. (2001). Deciding stability and mortality of piecewise affine dynamical systems. Theoretical Computer Science, 255(1-2), 687-696. https://doi.org/10.1016/S0304-3975(00)00399-6 (Original work published 2001)