An algorithmic approach to chain recurrence

In this paper we give a new definition of the chain recurrent set of a continuous map using finite spatial discretizations. This approach allows for an algorithmic construction of isolating blocks for the components of Morse decompositions which approximate the chain recurrent set arbitrarily closely as well as discrete approximations of Conley's Lyapunov function. This is a natural framework in which to develop computational techniques for the analysis of qualitative dynamics including rigorous computer-assisted proofs. © 2005 SFoCM. Conley's Fundamental Decomposition Theorem and its extension to Morse decompositions is a powerful tool in dynamical systems theory. However, the framework on which the standard theory is built does not lead naturally to an algorithmic or computational approach for the approximation of the chain recurrent set, i.e., generation of Morse decompositions or the approximation of a Lyapunov function for the gradient-like part of the system. One can approximate the chain recurrent set by the ε-chain recurrent set for finite ε > 0, but there are no algorithmic or computational techniques for computing this set directly. In this paper, we present an alternative approach based on finite discretizations and combinatorial multivalued maps. This approach has several advantages. The basic elements of the theory can be proved in a straightforward manner. Moreover, the methods are inherently combinatorial and hence algorithmic. The framework leads naturally to computational techniques for analyzing qualitative dynamics including rigorous computer-assisted proofs, see, e.g., [12], [16], [4], [5]. © 2005 SFoCM.