Deciding stability and mortality of piecewise affine dynamical systems

In this paper we study problems such as: given a discrete time dynamical sy stem of the form x(t + 1)= f(x(t)) where f: R-n --> R-n is a piecewise affi ne function, decide whether all trajectories converge to 0. We show in our main theorem that this Attractivity Problem is undecidable as soon as n gre ater than or equal to2. The same is true of two related problems: Stability (is the dynamical system globally asymptotically stable?) and Mortality (d o all trajectories go through 0?). We then show that AM-activity and Stabil ity become decidable in dimension 1 for continuous functions. (C) 2001 Else vier Science B.V. All rights reserved.