Symbolic dynamics

Last updated

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.

Contents

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

Concepts such as heteroclinic orbits and homoclinic orbits have a particularly simple representation in symbolic dynamics.

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

<span class="mw-page-title-main">Dynamical systems theory</span> Area of mathematics used to describe the behavior of complex dynamical systems

Dynamical systems theory is an area of mathematics used to describe the behavior of complex dynamical systems, usually by employing differential equations or difference equations. When differential equations are employed, the theory is called continuous dynamical systems. From a physical point of view, continuous dynamical systems is a generalization of classical mechanics, a generalization where the equations of motion are postulated directly and are not constrained to be Euler–Lagrange equations of a least action principle. When difference equations are employed, the theory is called discrete dynamical systems. When the time variable runs over a set that is discrete over some intervals and continuous over other intervals or is any arbitrary time-set such as a Cantor set, one gets dynamic equations on time scales. Some situations may also be modeled by mixed operators, such as differential-difference equations.

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

In mathematics, more particularly in the fields of dynamical systems and geometric topology, an Anosov map on a manifold M is a certain type of mapping, from M to itself, with rather clearly marked local directions of "expansion" and "contraction". Anosov systems are a special case of Axiom A systems.

In mathematics, specifically in topology, a pseudo-Anosov map is a type of a diffeomorphism or homeomorphism of a surface. It is a generalization of a linear Anosov diffeomorphism of the torus. Its definition relies on the notion of a measured foliation introduced by William Thurston, who also coined the term "pseudo-Anosov diffeomorphism" when he proved his classification of diffeomorphisms of a surface.

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.

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, ergodicity expresses the idea that a point of a moving system, either a dynamical system or a stochastic process, will eventually visit all parts of the space that the system moves in, in a uniform and random sense. This implies that the average behavior of the system can be deduced from the trajectory of a "typical" point. Equivalently, a sufficiently large collection of random samples from a process can represent the average statistical properties of the entire process. Ergodicity is a property of the system; it is a statement that the system cannot be reduced or factored into smaller components. Ergodic theory is the study of systems possessing ergodicity.

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.

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.

<span class="mw-page-title-main">Gustav A. Hedlund</span> American mathematician

Gustav Arnold Hedlund, an American mathematician, was one of the founders of symbolic and topological dynamics.

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

<span class="mw-page-title-main">Rufus Bowen</span> American mathematician

Robert Edward "Rufus" Bowen was an 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.

<span class="mw-page-title-main">Mladen Bestvina</span> Croatian-American mathematician

Mladen Bestvina is a Croatian-American mathematician working in the area of geometric group theory. He is a Distinguished Professor in the Department of Mathematics at the University of Utah.

The Michael Brin Prize in Dynamical Systems, abbreviated as the Brin Prize, is awarded to mathematicians who have made outstanding advances in the field of dynamical systems and are within 14 years of their PhD. The prize is endowed by and named after Michael Brin, whose son Sergey Brin is a co-founder of Google. Michael Brin is a retired mathematician at the University of Maryland and a specialist in dynamical systems.

References

  1. Hadamard, J. (1898). "Les surfaces à courbures opposées et leurs lignes géodésiques" (PDF). J. Math. Pures Appl. 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