In mathematics, symbolic dynamics is the practice of modeling a topological or smooth dynamical system by a discrete space consisting of infinite sequences of abstract symbols, each of which corresponds to a state of the system, with the dynamics (evolution) given by the shift operator. Formally, a Markov partition is used to provide a finite cover for the smooth system; each set of the cover is associated with a single symbol, and the sequences of symbols result as a trajectory of the system moves from one covering set to another.
The idea goes back to Jacques Hadamard's 1898 paper on the geodesics on surfaces of negative curvature. It was applied by Marston Morse in 1921 to the construction of a nonperiodic recurrent geodesic. Related work was done by Emil Artin in 1924 (for the system now called Artin billiard), Pekka Myrberg, Paul Koebe, Jakob Nielsen, G. A. Hedlund.
The first formal treatment was developed by Morse and Hedlund in their 1938 paper. George Birkhoff, Norman Levinson and the pair Mary Cartwright and J. E. Littlewood have applied similar methods to qualitative analysis of nonautonomous second order differential equations.
The theory was further advanced in the 1960s and 1970s, notably, in the works of Steve Smale and his school, and of Yakov Sinai and the Soviet school of ergodic theory. A spectacular application of the methods of symbolic dynamics is Sharkovskii's theorem about periodic orbits of a continuous map of an interval into itself (1964).
Symbolic dynamics originated as a method to study general dynamical systems; now its techniques and ideas have found significant applications in data storage and transmission, linear algebra, the motions of the planets and many other areas. The distinct feature in symbolic dynamics is that time is measured in discrete intervals. So at each time interval the system is in a particular state. Each state is associated with a symbol and the evolution of the system is described by an infinite sequence of symbols—represented effectively as strings. If the system states are not inherently discrete, then the state vector must be discretized, so as to get a coarse-grained description of the system.
- J. Hadamard (1898). "Les surfaces à courbures opposées et leurs lignes géodésiques" (PDF). J.Math.Pures Appl. 5 (4): 27–73.
- M. Morse and G. A. Hedlund (1938). "Symbolic Dynamics". American Journal of Mathematics 60: 815–866. doi:10.2307/2371264. JSTOR 2371264.
- Smale, S. (1967). "Differentiable dynamical systems". Bulletin of the American Mathematical Society 73 (6): 747. doi:10.1090/S0002-9904-1967-11798-1.
- Chacon, R. V. (1978). "Book Review: Introduction to ergodic theory". Bulletin of the American Mathematical Society 84 (4): 656. doi:10.1090/s0002-9904-1978-14515-7.
- Hao, Bailin (1989). Elementary Symbolic Dynamics and Chaos in Dissipative Systems. World Scientific. ISBN 9971-5-0682-3.
- Bruce Kitchens, Symbolic dynamics. One-sided, two-sided and countable state Markov shifts. Universitext, Springer-Verlag, Berlin, 1998. x+252 pp. ISBN 3-540-62738-3 MR 1484730
- Lind, Douglas; Marcus, Brian (1995). An introduction to symbolic dynamics and coding. Cambridge University Press. ISBN 0-521-55124-2. MR 1369092. Zbl 1106.37301.
- G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system. Math. Systems Theory, Vol. 3, No. 4 (1969) 320–3751
- Teschl, Gerald (2012). Ordinary Differential Equations and Dynamical Systems. Providence: American Mathematical Society. ISBN 978-0-8218-8328-0.
- ChaosBook.org Chapter "Transition graphs"