Symbolic dynamics

Last updated

In mathematics, symbolic dynamics is the study of dynamical systems defined on a discrete space consisting of infinite sequences of abstract symbols. The evolution of the dynamical system is defined as a simple shift of the sequence.

Contents

Because of their explicit, discrete nature, such systems are often relatively easy to characterize and understand. They form a key tool for studying topological or smooth dynamical systems, because in many important cases it is possible to reduce the dynamics of a more general dynamical system to a symbolic system. To do so, 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.

History

The idea goes back to Jacques Hadamard's 1898 paper on the geodesics on surfaces of negative curvature. [1] 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. [2] 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.

Claude Shannon used symbolic sequences and shifts of finite type in his 1948 paper A mathematical theory of communication that gave birth to information theory.

During the late 1960s the method of symbolic dynamics was developed to hyperbolic toral automorphisms by Roy Adler and Benjamin Weiss, [3] and to Anosov diffeomorphisms by Yakov Sinai who used the symbolic model to construct Gibbs measures. [4] In the early 1970s the theory was extended to Anosov flows by Marina Ratner, and to Axiom A diffeomorphisms and flows by Rufus Bowen.

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).

Examples

Consider the set of two-sided infinite sequences on two symbols, 0 and 1. A typical element in this set looks like: (..., 0, 1, 0, 0, 1, 0, 1, ... )

There will be exactly two fixed points under the shift map: the sequence of all zeroes, and the sequence of all ones. A periodic sequence will have a periodic orbit. For instance, the sequence (..., 0, 1, 0, 1, 0, 1, 0, 1, ...) will have period two.

More complex concepts such as heteroclinic orbits and homoclinic orbits also have simple descriptions in this system. For example, any sequence that has only a finite number of ones will have a homoclinic orbit, tending to the sequence of all zeros in forward and backward iterations.

Itinerary

Itinerary of point with respect to the partition is a sequence of symbols. It describes dynamic of the point. [5]

Applications

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[ citation needed ]. 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.

See also

Related Research Articles

<span class="mw-page-title-main">Dynamical system</span> Mathematical model of the time dependence of a point in space

In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space, such as in a parametric curve. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, the random motion of particles in the air, and the number of fish each springtime in a lake. The most general definition unifies several concepts in mathematics such as ordinary differential equations and ergodic theory by allowing different choices of the space and how time is measured. Time can be measured by integers, by real or complex numbers or can be a more general algebraic object, losing the memory of its physical origin, and the space may be a manifold or simply a set, without the need of a smooth space-time structure defined on it.

Ergodic theory is a branch of mathematics that studies statistical properties of deterministic dynamical systems; it is the study of ergodicity. In this context, "statistical properties" refers to properties which are expressed through the behavior of time averages of various functions along trajectories of dynamical systems. The notion of deterministic dynamical systems assumes that the equations determining the dynamics do not contain any random perturbations, noise, etc. Thus, the statistics with which we are concerned are properties of the dynamics.

In mathematics, a measure-preserving dynamical system is an object of study in the abstract formulation of dynamical systems, and ergodic theory in particular. Measure-preserving systems obey the Poincaré recurrence theorem, and are a special case of conservative systems. They provide the formal, mathematical basis for a broad range of physical systems, and, in particular, many systems from classical mechanics as well as systems in thermodynamic equilibrium.

<span class="mw-page-title-main">Horseshoe map</span> Class of chaotic maps

In the mathematics of chaos theory, a horseshoe map is any member of a class of chaotic maps of the square into itself. It is a core example in the study of dynamical systems. The map was introduced by Stephen Smale while studying the behavior of the orbits of the van der Pol oscillator. The action of the map is defined geometrically by squishing the square, then stretching the result into a long strip, and finally folding the strip into the shape of a horseshoe.

<span class="mw-page-title-main">John N. Mather</span> American mathematician

John Norman Mather was a mathematician at Princeton University known for his work on singularity theory and Hamiltonian dynamics. He was descended from Atherton Mather (1663–1734), a cousin of Cotton Mather. His early work dealt with the stability of smooth mappings between smooth manifolds of dimensions n and p. He determined the precise dimensions (n,p) for which smooth mappings are stable with respect to smooth equivalence by diffeomorphisms of the source and target.

In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite state machine. The most widely studied shift spaces are the subshifts of finite type.

<span class="mw-page-title-main">Bifurcation theory</span> Study of sudden qualitative behavior changes caused by small parameter changes

Bifurcation theory is the mathematical study of changes in the qualitative or topological structure of a given family of curves, such as the integral curves of a family of vector fields, and the solutions of a family of differential equations. Most commonly applied to the mathematical study of dynamical systems, a bifurcation occurs when a small smooth change made to the parameter values of a system causes a sudden 'qualitative' or topological change in its behavior. Bifurcations occur in both continuous systems and discrete systems.

In mathematics, structural stability is a fundamental property of a dynamical system which means that the qualitative behavior of the trajectories is unaffected by small perturbations.

In mathematics, the Bernoulli scheme or Bernoulli shift is a generalization of the Bernoulli process to more than two possible outcomes. Bernoulli schemes appear naturally in symbolic dynamics, and are thus important in the study of dynamical systems. Many important dynamical systems exhibit a repellor that is the product of the Cantor set and a smooth manifold, and the dynamics on the Cantor set are isomorphic to that of the Bernoulli shift. This is essentially the Markov partition. The term shift is in reference to the shift operator, which may be used to study Bernoulli schemes. The Ornstein isomorphism theorem shows that Bernoulli shifts are isomorphic when their entropy is equal.

<span class="mw-page-title-main">Homoclinic orbit</span> Closed loop through a phase space

In the study of dynamical systems, a homoclinic orbit is a path through phase space which joins a saddle equilibrium point to itself. More precisely, a homoclinic orbit lies in the intersection of the stable manifold and the unstable manifold of an equilibrium. It is a heteroclinic orbit–a path between any two equilibrium points–in which the endpoints are one and the same.

<span class="mw-page-title-main">Heteroclinic orbit</span> Path between equilibrium points in a phase space

In mathematics, in the phase portrait of a dynamical system, a heteroclinic orbit is a path in phase space which joins two different equilibrium points. If the equilibrium points at the start and end of the orbit are the same, the orbit is a homoclinic orbit.

In mathematics, the Ornstein isomorphism theorem is a deep result in ergodic theory. It states that if two Bernoulli schemes have the same Kolmogorov entropy, then they are isomorphic. The result, given by Donald Ornstein in 1970, is important because it states that many systems previously believed to be unrelated are in fact isomorphic; these include all finite stationary stochastic processes, including Markov chains and subshifts of finite type, Anosov flows and Sinai's billiards, ergodic automorphisms of the n-torus, and the continued fraction transform.

In mathematics, Smale's axiom A defines a class of dynamical systems which have been extensively studied and whose dynamics is relatively well understood. A prominent example is the Smale horseshoe map. The term "axiom A" originates with Stephen Smale. The importance of such systems is demonstrated by the chaotic hypothesis, which states that, 'for all practical purposes', a many-body thermostatted system is approximated by an Anosov system.

<span class="mw-page-title-main">Arnold's cat map</span> Chaotic map from the torus into itself

In mathematics, Arnold's cat map is a chaotic map from the torus into itself, named after Vladimir Arnold, who demonstrated its effects in the 1960s using an image of a cat, hence the name. It is a simple and pedagogical example for hyperbolic toral automorphisms.

A Markov partition in mathematics is a tool used in dynamical systems theory, allowing the methods of symbolic dynamics to be applied to the study of hyperbolic dynamics. By using a Markov partition, the system can be made to resemble a discrete-time Markov process, with the long-term dynamical characteristics of the system represented as a Markov shift. The appellation 'Markov' is appropriate because the resulting dynamics of the system obeys the Markov property. The Markov partition thus allows standard techniques from symbolic dynamics to be applied, including the computation of expectation values, correlations, topological entropy, topological zeta functions, Fredholm determinants and the like.

In mathematics, topological dynamics is a branch of the theory of dynamical systems in which qualitative, asymptotic properties of dynamical systems are studied from the viewpoint of general topology.

The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A. Hedlund, and Roger Lyndon; in his 1969 paper stating the theorem, Hedlund credited Curtis and Lyndon as co-discoverers. It has been called "one of the fundamental results in symbolic dynamics".

In dynamical systems theory, an area of pure mathematics, a Morse–Smale system is a smooth dynamical system whose non-wandering set consists of finitely many hyperbolic equilibrium points and hyperbolic periodic orbits and satisfying a transversality condition on the stable and unstable manifolds. Morse–Smale systems are structurally stable and form one of the simplest and best studied classes of smooth dynamical systems. They are named after Marston Morse, the creator of the Morse theory, and Stephen Smale, who emphasized their importance for smooth dynamics and algebraic topology.

<span class="mw-page-title-main">Rufus Bowen</span> American mathematician (1947–1978)

Robert Edward "Rufus" Bowen was an American internationally known professor in the Department of Mathematics at the University of California, Berkeley, who specialized in dynamical systems theory. Bowen's work dealt primarily with axiom A systems, but the methods he used while exploring topological entropy, symbolic dynamics, ergodic theory, Markov partitions, and invariant measures "have application far beyond the axiom A systems for which they were invented." The Bowen Lectures at the University of California, Berkeley, are given in his honor.

Zhihong "Jeff" Xia is a Chinese-American mathematician.

References

  1. ↑ Hadamard, J. (1898). "Les surfaces à courbures opposées et leurs lignes géodésiques" (PDF). J. Math. Pures Appl. (in French). 5 (4): 27–73.
  2. ↑ Morse, M.; Hedlund, G. A. (1938). "Symbolic Dynamics". American Journal of Mathematics. 60 (4): 815–866. doi:10.2307/2371264. JSTOR   2371264.
  3. ↑ Adler, R.; Weiss, B. (1967). "Entropy, a complete metric invariant for automorphisms of the torus". PNAS . 57 (6): 1573–1576. Bibcode:1967PNAS...57.1573A. doi: 10.1073/pnas.57.6.1573 . JSTOR   57985. PMC   224513 . PMID   16591564.
  4. ↑ Sinai, Y. (1968). "Construction of Markov partitionings". Funkcional. Anal. I Priložen. 2 (3): 70–80.
  5. ↑ Mathematics of Complexity and Dynamical Systems by Robert A. Meyers. Springer Science & Business Media, 2011, ISBN   1461418054, 9781461418054

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.