Symbolic dynamics
Encyclopedia
In mathematics
, symbolic dynamics is the practice of modeling a topological or smooth dynamical system
by a discrete space consisting of infinite sequence
s 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 of the covering sets to another.
's 1898 paper on the geodesic
s on surface
s 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), P. J. 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 M. L. Cartwright–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
.
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).
s and homoclinic orbit
s have a particularly simple representation in symbolic dynamics.
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, symbolic dynamics is the practice of modeling a topological or smooth dynamical system
Dynamical system
A dynamical system is a concept in mathematics where a fixed rule describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a...
by a discrete space consisting of infinite sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
s of abstract symbols, each of which corresponds to a state of the system, with the dynamics (evolution) given by the shift operator
Shift operator
In mathematics, and in particular functional analysis, the shift operator or translation operator is an operator that takes a function to its translation . In time series analysis, the shift operator is called the lag operator....
. Formally, a Markov partition
Markov partition
A Markov partition is a tool used in dynamical systems theory, allowing the methods of symbolic dynamics to be applied to the study of hyperbolic systems. By using a Markov partition, the system can be made to resemble a discrete-time Markov process, with the long-term dynamical characteristics...
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 of the covering sets to another.
History
The idea goes back to Jacques HadamardJacques Hadamard
Jacques Salomon Hadamard FRS was a French mathematician who made major contributions in number theory, complex function theory, differential geometry and partial differential equations.-Biography:...
's 1898 paper on the geodesic
Geodesic
In mathematics, a geodesic is a generalization of the notion of a "straight line" to "curved spaces". In the presence of a Riemannian metric, geodesics are defined to be the shortest path between points in the space...
s on surface
Surface
In mathematics, specifically in topology, a surface is a two-dimensional topological manifold. The most familiar examples are those that arise as the boundaries of solid objects in ordinary three-dimensional Euclidean space R3 — for example, the surface of a ball...
s of negative curvature
Curvature
In mathematics, curvature refers to any of a number of loosely related concepts in different areas of geometry. Intuitively, curvature is the amount by which a geometric object deviates from being flat, or straight in the case of a line, but this is defined in different ways depending on the context...
. It was applied by Marston Morse
Marston Morse
Harold Calvin Marston Morse was an American mathematician best known for his work on the calculus of variations in the large, a subject where he introduced the technique of differential topology now known as Morse theory...
in 1921 to the construction of a nonperiodic recurrent geodesic. Related work was done by Emil Artin
Emil Artin
Emil Artin was an Austrian-American mathematician of Armenian descent.-Parents:Emil Artin was born in Vienna to parents Emma Maria, née Laura , a soubrette on the operetta stages of Austria and Germany, and Emil Hadochadus Maria Artin, Austrian-born of Armenian descent...
in 1924 (for the system now called Artin billiard), P. J. Myrberg, Paul Koebe
Paul Koebe
Paul Koebe was a 20th-century German mathematician. His work dealt exclusively with the complex numbers, his most important results being on the uniformization of Riemann surfaces in a series of four papers in 1907–1909. He did his thesis at Berlin, where he worked under Herman Schwarz...
, Jakob Nielsen
Jakob Nielsen (mathematician)
Jakob Nielsen was a Danish mathematician known for his work on automorphisms of surfaces. He was born in the village Mjels on the island of Als in North Schleswig, in modern day Denmark. His mother died when he was 3, and in 1900 he went to live with his aunt and was enrolled in the Realgymnasium...
, G. A. Hedlund.
The first formal treatment was developed by Morse and Hedlund in their 1938 paper. George Birkhoff, Norman Levinson and M. L. Cartwright–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
A Mathematical Theory of Communication
"A Mathematical Theory of Communication" is an influential 1948 article by mathematician Claude E. Shannon. As of November 2011, Google Scholar has listed more than 48,000 unique citations of the article and the later-published book version...
that gave birth to information theory
Information theory
Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...
.
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
Ergodic theory
Ergodic theory is a branch of mathematics that studies dynamical systems with an invariant measure and related problems. Its initial development was motivated by problems of statistical physics....
. 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 orbitHeteroclinic orbit
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...
s and homoclinic orbit
Homoclinic orbit
In mathematics, a homoclinic orbit is a trajectory of a flow of a dynamical system 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.Homoclinic orbits and homoclinic points...
s have a particularly simple representation in symbolic dynamics.
Applications
Symbolic dynamics originated as a method to study general dynamical systems; now its techniques and ideas have found significant applications in data storageData storage device
thumb|200px|right|A reel-to-reel tape recorder .The magnetic tape is a data storage medium. The recorder is data storage equipment using a portable medium to store the data....
and transmission
Data transmission
Data transmission, digital transmission, or digital communications is the physical transfer of data over a point-to-point or point-to-multipoint communication channel. Examples of such channels are copper wires, optical fibres, wireless communication channels, and storage media...
, linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
, the motions of the planets and many other areas. The distinct feature in symbolic dynamics is that time is measured in discrete
Discrete time
Discrete time is the discontinuity of a function's time domain that results from sampling a variable at a finite interval. For example, consider a newspaper that reports the price of crude oil once every day at 6:00AM. The newspaper is described as sampling the cost at a frequency of once per 24...
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
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
of symbols — represented effectively as strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
. If the system states are not inherently discrete, then the state vector
State vector
*A state vector in general control systems describes the observed states of an object in state space, e.g. in variables of the degrees of freedom for motion *A state vector in general control systems describes the observed states of an object in state space, e.g. in variables of the degrees of...
must be discretized, so as to get a coarse-grained description of the system.
Further reading
- 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
- Douglas Lind and Brian Marcus, An Introduction to Symbolic Dynamics and Coding. Cambridge University PressCambridge University PressCambridge University Press is the publishing business of the University of Cambridge. Granted letters patent by Henry VIII in 1534, it is the world's oldest publishing house, and the second largest university press in the world...
, Cambridge, 1995. xvi+495 pp. ISBN 0-521-55124-2 - M. MorseMarston MorseHarold Calvin Marston Morse was an American mathematician best known for his work on the calculus of variations in the large, a subject where he introduced the technique of differential topology now known as Morse theory...
and G. A. Hedlund, Symbolic Dynamics, American Journal of Mathematics, 60 (1938) 815–866 - G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system. Math. Systems Theory, Vol. 3, No. 4 (1969) 320–3751