Symbolic dynamics

In mathematics, symbolic dynamics is the practice of modelling a dynamical system by a space consisting of infinite sequences of abstract symbols, each sequence corresponding to a state of the system, and a shift operator corresponding to the dynamics.

Shifts of finite type

The most widely studied shift spaces are the shifts of finite type.

Let $S=\{1,2,\cdots ,k\}$ be a finite set of symbols, and let A be a kxk matrix with entries in {0,1}. We define the one-sided shift of finite type by:

$\Sigma _{A}^{+}=\left\{(x_{j})_{j=0}^{\infty }:A_{x_{j}x_{j+1}}=1,j\in \mathbb {N} \right\}$

This means the space of all sequences of symbols such that the symbol i can be followed by the symbol j only if the (i,j)^th entry of the matrix A is 1. If all entries are 1, we call this the full one sided shift of finite type.

The two-sided shift of finite type is defined analogously:

$\Sigma _{A}=\left\{(x_{j})_{j=-\infty }^{\infty }:A_{x_{j}x_{j+1}}=1,j\in \mathbb {Z} \right\}$

This is the space of all bi-infinite sequences under the same condition.

The shift operator $\sigma$ maps a sequence in the one- or two-sided shift to another by shifting all symbols to the left, i.e. $(\sigma (x))_{j}=x_{j+1}$. Clearly this map is only invertible in the case of the two-sided shift.

One can define a metric on a shift space by considering two points to be "close" if they have many initial symbols in common. In fact, both the one- and two-sided shift spaces are compact metric spaces.

External links

• An Introduction to Symbolic Dynamics and Coding - a textbook by Douglas Lind and Brian Marcus
• General overview