In mathematics, subshifts of finite type are shift spaces defined by a finite set of forbidden words. They are used to model dynamical systems, and in particular are 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.
Motivating examples One example of a (one-sided) shift of finite type is the set of all sequences, infinite on one end only, that can be made up of the letters A , B {\displaystyle A,B} , like A A A ⋯ , A B A B ⋯ , … {\displaystyle AAA\cdots ,ABAB\cdots ,\dots } . This is known as a full shift and is denoted by { A , B } N {\displaystyle \{A,B\}^{\mathbb {N} }} . By forbidding the word B B {\displaystyle BB} , one defines a shift of finite type Σ = { ( x 0 , x 1 , x 2 , … ) ∣ x i x i + 1 ≠ B B } {\displaystyle \Sigma =\{(x_{0},x_{1},x_{2},\ldots )\mid x_{i}x_{i+1}\neq BB\}} called the golden shift, so-called because the numbers of legal words of length n {\displaystyle n} are the Fibonacci numbers. Two-sided shifts of finite type are similar, but consist of sequences that are infinite on both ends. A subshift can be defined by a directed graph on the letters, such as the graph A → B → C → A {\displaystyle A\to B\to C\to A} . It consists of sequences whose transitions between consecutive letters are only those allowed by the graph. For this example, the subshift consists of only three one-sided sequences: A B C A B C ⋯ , B C A B C A ⋯ , C A B C A B ⋯ {\displaystyle ABCABC\cdots ,BCABCA\cdots ,CABCAB\cdots } . Similarly, the two-sided subshift described by this graph consists of only three two-sided sequences. Other directed graphs on the same letters produce other subshifts. For example, adding another arrow A → C {\displaystyle A\to C} to the graph produces a subshift that, instead of containing three sequences, contains an uncountably infinite number of sequences. Up to a local recoding of letters, every subshift of finite type can be described by such a directed graph.
Definition Let A {\displaystyle {\mathcal {A}}} be a finite set of n {\displaystyle n} symbols (alphabet). Let X {\displaystyle X} denote the set A Z {\displaystyle {\mathcal {A}}^{\mathbb {Z} }} of all bi-infinite sequences of elements of A {\displaystyle {\mathcal {A}}} together with the shift operator T {\displaystyle T} . We endow A {\displaystyle {\mathcal {A}}} with the discrete topology and X {\displaystyle X} with the product topology. A symbolic flow or subshift is a closed T {\displaystyle T} -invariant subset Y {\displaystyle Y} of X {\displaystyle X} and the associated language L Y {\displaystyle {\mathcal {L}}_{Y}} is the set of finite subwords of elements of Y {\displaystyle Y} . Let F {\displaystyle F} be a finite set of words in the alphabet A {\displaystyle {\mathcal {A}}} , which are called forbidden words. The associated subshift of finite type is defined to be the space
Σ F = { ( x 0 , x 1 , x 2 , … ) ∣ ∀ i , k ≥ 0 , x i x i + 1 ⋯ x i + k ∉ F } {\displaystyle \Sigma _{F}=\{(x_{0},x_{1},x_{2},\ldots )\mid \forall i,k\geq 0,x_{i}x_{i+1}\cdots x_{i+k}\notin F\}}
… excerpt ends here. Continue reading the full article.
