View source for Symbolic dynamics

{{TEX|done}}

Symbolic dynamics in the narrow sense is the investigation of the topological [[Bernoulli automorphism]] $\sigma$ defined below, its invariant closed subsets, its invariant measures, etc. The topological Bernoulli automorphism $\sigma$ acts in the space $\Omega$ of infinite two-sided sequences of symbols from an alphabet $A$ (usually finite), provided with the direct product topology as an infinite number of copies of $A$ (it is usual to take the discrete topology in each copy). Namely, $\sigma$ takes a sequence $\omega = (\omega_i)$ to $\omega' = (\omega'_i)$, where $\omega_i' = \omega_{i+1}$ ( "shift the sequence one place to the left" ). An obvious generalization is the action of a group (or semi-group) $G$ on the space $A^G$ of functions from $G$ to $A$.

Let certain pairs $(a,b)$ of symbols from $A$ be declared  "admissible" . All sequences $\omega_i$ for which for all $i$ the pair $(\omega_i,\omega_{i+1})$ is admissible form a closed ($\sigma$-) invariant subset $\Omega_1 \subset \Omega$. This is the most important example of an invariant subset of the topological Bernoulli automorphism. The [[dynamical system]] in $\Omega_1$ generated by the shift $\sigma{\downharpoonright}_{\Omega_1}$ is called a topological Markov chain.

Symbolic dynamics in the broad sense is the application of symbolic dynamics in the narrow sense to the investigation of dynamical systems which themselves are defined completely independently of $\Omega$ and $\sigma$.

====References====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  V.M. Alekseev,   "Symbolic dynamics. Eleventh Summer School in Math." , '''1''' , Kiev  (1976)  (In Russian)</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">  R. Bowen,   "Equilibrium states and the ergodic theory of Anosov diffeomorphisms" , ''Lect. notes in math.'' , '''470''' , Springer  (1975)  {{ZBL|0308.28010}}; 2nd ed.
 (2008) {{ISBN|978-3-540-77605-5}} {{ZBL|1172.37001}}</TD></TR>
</table>

====Comments====
A1) Instead of  "topological Bernoulli automorphism"  usually the term shift transformation (or simply shift) is employed. Shift systems and their closed invariant subspaces (usually called subshifts) form an important family of cascades with many applications, also outside of dynamical systems theory.

Both in [[ergodic theory]] and in [[topological dynamics]] many important examples and counter-examples are defined by subshifts, which are often obtained as the closure of the orbit of a certain point in  $  \Omega $, 
the point in question being an infinite two-sided sequence  $  \omega = \{ \omega _{i} \} $
with special combinatorial properties. For instance, the Morse–Thue sequence is the two-sided sequence  $  \{ \mu _{i} \} $
over the alphabet  $  \{ 0,\  1 \} $
such that  $  \mu _ {-i} = \mu _ {i-1} $
for all  $  i \geq 1 $, 
and where the  $  \mu _{i} $
for  $  i \geq 0 $
are given as follows: if the  "block"  of the first  $  2 ^{n} $
entries is denoted by  $  Q _{n} $, 
then  $  Q _{0} = 0 $
and  $  Q _ {n+1} $
is the concatenation of the blocks  $  Q _{n} $
and  $  \overline{Q}\; _{n} $; 
here  $  \overline{Q}\; _{n} $
is obtained from  $  Q _{n} $
by interchanging all  $  0 $'
s and  $  1 $'
s. Thus, the sequence of non-negative coordinates of  $  \mu $
is  $  0110 \  1001 \  1001 \  0110 \dots $. 
An alternative definition is: Let  $  \alpha _{n} $
be the number of one's in the binary expansion of  $  n $; 
then  $  \mu _{n} = \alpha _{n} $(
mod  $  2 $) 
for  $  n \geq 0 $. 
This sequence defines a point in  $  \Omega $
which is almost periodic but not periodic; see [[#References|[a10]]], Chapt. 12. For general results on shift systems, consult [[#References|[a11]]], .

The topological Markov chains defined above are also called subshifts of finite type. Such a subshift can be characterized by an  $  (m \times m) $-
matrix  $  M $, 
where  $  m $
is the number of elements in the alphabet  $  A $
under consideration, as follows: Let  $  A = \{ a _{1} \dots a _{m} \} $; 
then a pair  $  (a _{i} ,\  a _{j} ) $
is admissible if and only if the entry  $  M _ {ij} $
of  $  M $
is 1; the other entries of  $  M $
are  $  0 $(
the transition matrix of the topological Markov chain). Properties of the topological Markov chain can often be expressed in terms of the associated transition matrix. For example, the [[topological entropy]] of a topological Markov chain equals  $   \mathop{\rm log}\nolimits \  \lambda $, 
where  $  \lambda $
is the largest positive eigenvalue of the transition matrix. For the classification of topological Markov chains, see [[#References|[a2]]] and [[#References|[a8]]].

Related with the topological Markov chains are the sofic systems ([[#References|[a5]]], ). A sofic system is a subshift  $  \Omega _{1} $
for which there exist a topological Markov chain  $  \Omega _{2} $
and a continuous surjection  $  \phi : \  \Omega _{2} \rightarrow \Omega _{1} $
which commutes with the shift transformations in  $  \Omega _{2} $
and  $  \Omega _{1} $. 
For problems related with the classification of sofic systems, see [[#References|[a7]]].

For applications of topological Markov chains and sofic systems for the construction of codes in information theory, see [[#References|[a1]]], . As another example one should mention that the Morse–Thue sequence was used, among others, to prove the existence of recurrent non-closed geodesics on certain manifolds of negative curvature [[#References|[a21]]], but also to disprove Burnside's conjecture that a bounded group is finite ( cf. [[Burnside problem|Burnside problem]] 2).

In ergodic theory shift systems play an almost  "universal"  role. An important class is formed by the Bernoulli shifts, also called Bernoulli automorphisms; see e.g. [[#References|[a24]]]. Many systems that are defined in another way turn out to be isomorphic to Bernoulli shifts (e.g., geodesic flows on surfaces of negative curvature, [[#References|[a22]]]). In this context also the Jewett–Krieger theorem (cf. [[Strong ergodicity|Strong ergodicity]]) should be mentioned. For the ergodic properties of the Morse (–Thue) system, see e.g. [[#References|[a15]]]; it is uniquely ergodic [[#References|[a16]]], [[#References|[a17]]]. Other publications dealing directly or indirectly with the ergodic theory of shift systems are [[#References|[a2]]], [[#References|[a3]]], [[#References|[a9]]], [[#References|[a13]]] [[#References|[a14]]], [[#References|[a23]]].

A2) Symbolic dynamics in the broad sense rests on the following principle. Suppose the phase space  $  W $
of a cascade  $  f: \  W \rightarrow W $
is partitioned into finitely many disjoint sets  $  W _{1} \dots W _{n} $. 
Then for every  $  w \in W $
and  $  n \in \mathbf Z $
there is a unique  $  \phi (n,\  w) \in \{ 1 \dots n \} $
such that  $  f ^ {\  n} (w) \in W _ {\phi (n,w)} $. 
The sequence  $  \Phi (w) = \{ \phi (n,\  w) :\   n \in \mathbf Z \} $
— also called the itinerary of  $  w $
— can be considered as an element of the shift system  $  \Omega $
over the alphabet  $  A = \{ 1 \dots n \} $, 
and the mapping  $  \Phi : \  W \rightarrow \Omega $
satisfies the equality  $  \Phi (f(w) ) = \sigma ( \Phi (w) ) $
for all  $  w \in W $. 
In practice this description is too restrictive. Then one tries to construct a so-called Markov partition of  $  W $, 
which is not a partition at all, but a covering of  $  W $
by closed subsets with mutually disjoint interiors (subject to certain additional conditions which are too complicated to state here). Associated with such a Markov partition is a transition matrix  $  M $, 
defined as follows:  $  M _ {ij} = 0 $
or  $  1 $
according to whether  $   \mathop{\rm int}\nolimits \  W _{i} \cap f ^ {\  -1} (  \mathop{\rm int}\nolimits \  W _{j} ) $
is empty or not. Under suitable conditions on  $  f $(
including that the phase space is a [[Hyperbolic set|hyperbolic set]]) this matrix defines a topological Markov chain  $  \Omega _{M} $, 
for which it is possible to define a continuous surjection  $  pi: \  \Omega _{M} \rightarrow W $
such that  $  f\circ pi= pi\circ \sigma $, 
$  \pi $
is  $  1 $-
$  1 $
on a dense  $  G _ \delta  $-
set in  $  \Omega _{M} $
and  $  f ^ {\  n} ( \pi ( \omega ) ) \in W _ {\omega _ n} $
for all  $  \omega \in \Omega $
and all  $  n \in \mathbf Z $, 
i.e.  $  \omega = \{ \omega _{n} \} $
is an itinerary of  $  \pi ( \omega ) $. 
This mapping may be used to study the given cascade both from a topological and a measure-theoretic point of view, using the special properties of the topological Markov chain  $  \Omega _{M} $.


Important instances of cascades for which this method has been successful are, e.g., hyperbolic automorphisms of the torus [[#References|[a3]]], Anosov diffeomorphisms (cf. [[Y-system| $  Y $-
system]]) [[#References|[a26]]], [[#References|[a27]]], and  "basic subsets"  in axiom- $  A $
diffeomorphisms [[#References|[a6]]] (see also [[#References|[2]]], [[#References|[a25]]] and [[#References|[a4]]]). (A diffeomorphism on a compact  $  C ^ \infty  $-
manifold is said to satisfy Axiom  $  A $
whenever the set of non-wandering points is hyperbolic and is the closure of the set of periodic points, cf. [[Non-wandering point|Non-wandering point]].)

Symbolic dynamics is also used for the analysis of chaotic behaviour of dynamical systems (cf. [[Chaos|Chaos]]; [[Fractals|Fractals]]; [[Strange attractor|Strange attractor]]). Related with symbolic dynamics is the  "kneading calculus"  for mappings of the interval [[#References|[a20]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.L. Adler,   D. Coppersmith,   M. Hassner,   "Algorithms for sliding block codes"  ''IEEE Trans. Inform. Theory'' , '''219'''  (1983)  pp. 5–22</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.L. Adler,   B. Marcus,   "Topological entropy and equivalence of dynamical systems"  ''Mem. Amer. Math. Soc.'' , '''219'''  (1979)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.L. Adler,   B. Weiss,   "Similarity of automorphisms of the torus"  ''Mem. Amer. Math. Soc.'' , '''98'''  (1970)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  V.M. Alekseev,   M.V. Yakobson,   "Symbolic dynamics and hyperbolic dynamic systems"  ''Physics Reports'' , '''75''' :  5  (1981)  pp. 287–325</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  B. Weiss,   "Subshifts of finite type and sofic systems"  ''Monatsh. Math.'' , '''77'''  (1973)  pp. 462–474</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  R. Bowen,   "Markov partitions for Axiom A diffeomorphisms"  ''Amer. J. Math.'' , '''92'''  (1970)  pp. 725–747</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  M. Boyle,   W. Krieger,   "Almost Markov and shift equivalent sofic systems"  J.C. Alexander (ed.) , ''Dynamical Systems (Proc. Maryland, 1986–7)'' , Springer  (1988)  pp. 33–93</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  M. Boyle,   B. Marcus,   P. Trow,   "Resolving maps and the dimension group for shifts of finite type"  ''Mem. Amer. Math. Soc.'' , '''377'''  (1987)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  C. Grillenberger,   "Ergodic theory on compact spaces" , Springer  (1976)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  G.H. Hedlund,   "Topological dynamics" , Amer. Math. Soc.  (1955)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  G.H. Hedlund,   "Endomorphisms and automorphisms of the shift dynamical system"  ''Math. Systems Theory'' , '''3'''  (1969)  pp. 320–375</TD></TR><TR><TD valign="top">[a12a]</TD> <TD valign="top">  G.H. Hedlund,   M. Morse,   "Symbolic dynamics I"  ''Amer. J. Math.'' , '''60'''  (1938)  pp. 815–866</TD></TR><TR><TD valign="top">[a12b]</TD> <TD valign="top">  G.H. Hedlund,   M. Morse,   "Symbolic dynamics II"  ''Amer. J. Math.'' , '''62'''  (1940)  pp. 1–42</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  K. Jacobs,   M. Keane,   "0–1 sequences of Toeplitz type"  ''Z. Warsch. verw. Geb.'' , '''13'''  (1969)  pp. 123–131</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  A. del Junco,   M. Keane,   B. Kitchens,   B. Marcus,   L. Swanson,   "Continuous homomorphisms of Bernoulli schemes"  A. Katok (ed.) , ''Ergodic Theory and Dynamical Systems'' , Birkhäuser  (1981)  pp. 91–111</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  S. Kakutani,   "Ergodic theory of shift transformations"  L. le Cam (ed.)  J. Neyman (ed.) , ''Proc. 5-th Berkeley Symp. Math. Probab. Stat. II'' , Univ. California Press  (1967)  pp. 405–414</TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top">  S. Kakutani,   "Strictly ergodic symbolic dynamical systems"  L. le Cam (ed.)  J. Neyman (ed.)  E.L. Scott (ed.) , ''Proc. 6-th Berkeley Symp. Math. Probab. Stat. II'' , Univ. California Press  (1972)  pp. 319–326</TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top">  M.Keane,   "Generalized Morse sequences"  ''Z. Warsch. verw. Geb.'' , '''10'''  (1968)  pp. 335–353</TD></TR><TR><TD valign="top">[a18a]</TD> <TD valign="top">  W. Krieger,   "On sofic systems I"  ''Israel J. Math.'' , '''48'''  (1984)  pp. 305–330</TD></TR><TR><TD valign="top">[a18b]</TD> <TD valign="top">  W. Krieger,   "On sofic systems II"  ''Israel J. Math.'' , '''60'''  (1987)  pp. 167–176</TD></TR><TR><TD valign="top">[a19]</TD> <TD valign="top">  B. Marcus,   "Sofic systems and encoding data"  ''IEEE Trans. Inform. Theory'' , '''31'''  (1985)  pp. 366–377</TD></TR><TR><TD valign="top">[a20]</TD> <TD valign="top">  J.W. Milnor,   R. Thurston,   "On iterated maps of the interval"  J.C. Alexander (ed.) , ''Dynamical Systems (Proc. Maryland, 1986–7)'' , ''Lect. notes in math.'' , '''1342''' , Springer  (1988)  pp. 465–563</TD></TR><TR><TD valign="top">[a21]</TD> <TD valign="top">  M. Morse,   "Recurrent geodesics on a surface of negative curvature"  ''Amer. J. Math.'' , '''43'''  (1921)  pp. 33–51</TD></TR><TR><TD valign="top">[a22]</TD> <TD valign="top">  D. Ornstein,   B. Weiss,   "Geodesic flows are Bernoullian"  ''Israel J. Math.'' , '''14'''  (1973)  pp. 184–198</TD></TR><TR><TD valign="top">[a23]</TD> <TD valign="top">  W.S. Parry,   S. Tuncel,   "Classification problems in ergodic theory" , Cambridge Univ. Press  (1982)</TD></TR><TR><TD valign="top">[a24]</TD> <TD valign="top">  P. Shields,   "The theory of Bernoulli shifts" , Univ. Chicago Press  (1973)</TD></TR><TR><TD valign="top">[a25]</TD> <TD valign="top">  M. Shub,   "Global stability of dynamical systems" , Springer  (1987)  (Translated from French)</TD></TR><TR><TD valign="top">[a26]</TD> <TD valign="top">  Ya. Sinai,   "Markov partitions and C-diffeomorphisms"  ''Funct. Anal. Appl.'' , '''2''' :  1  (1968)  pp. 64–89  ''Funkts. Anal. Prilozh.'' , '''2''' :  1  (1968)  pp. 64–89</TD></TR><TR><TD valign="top">[a27]</TD> <TD valign="top">  Ya. Sinai,   "Construction of Markov partitions"  ''Funct. Anal. Appl.'' , '''2''' :  2  (1968)  pp. 70–80  ''Funkts. Anal. Prilozh.'' , '''2''' :  3  (1968)  pp. 64–80</TD></TR></table>