Definition:Shift of Finite Type

Definition

Let $\mathbf A = \sqbrk a_k$ be a logical matrix for a $k \in \Z: k \ge 2$.

Let $\set {1, 2, \ldots, k}$ be given the discrete topology.

Let $X _\mathbf A$ be the subspace of the product space $\set {1, 2, \ldots, k} ^\Z$ defined as:

$X_\mathbf A = \set {x = \sequence {x_n}_{n \mathop \in \Z} : x_n \in \set {1, 2, \ldots, k}, a_{x_n, x_{n + 1} } = 1}$.

Let $\sigma_\mathbf A : X_\mathbf A \to X_\mathbf A$ be the forward shift operator, that is:

$\map {\sigma _{\mathbf A} } x := y$

where $y_n = x_{n + 1}$ for all $n \in \Z$.

Then the pair $\struct {X _\mathbf A, \sigma_\mathbf A}$ is called a shift of finite type.

$\struct {X _\mathbf A, \sigma_\mathbf A}$ is also called two-sided shift of finite type as well as topological Markov chain.

The mapping $\sigma_\mathbf A : X_\mathbf A \to X_\mathbf A$ is also called simply shift operator as well as shift.