Inmathematics,subshifts of finite type are used to modeldynamical systems, and in particular are the objects of study insymbolic dynamics andergodic theory. They also describe the set of all possible sequences executed by afinite-state machine. The most widely studiedshift spaces are the subshifts of finite type.

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${\displaystyle A,B,C}$, like${\displaystyle AAA\cdots ,ABAB\cdots ,\dots }$. A (two-sided) shift of finite type is similar, but consists of sequences that are infinite on both ends.

A subshift can be defined by a directed graph on these letters, such as the graph${\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:${\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${\displaystyle A\to C}$ to the graph produces a subshift that, instead of containing three sequences, containsan uncountably infinite number of sequences.

Given aMarkov transition matrix and an invariant distribution on the states, we can impose a probability measure on the set of subshifts. For example, consider the Markov chain given on the left on the states${\displaystyle A,B_1,B_2}$, with invariant distribution${\displaystyle \pi =(2/7,4/7,1/7)}$. If we "forget" the distinction between${\displaystyle B_1,B_2}$, we project this space of subshifts on${\displaystyle A,B_1,B_2}$ into another space of subshifts on${\displaystyle A,B}$, and this projection also projects the probability measure down to a probability measure on the subshifts on${\displaystyle A,B}$.

The curious thing is that the probability measure on the subshifts on${\displaystyle A,B}$ is not created by a Markov chain on${\displaystyle A,B}$, not even multiple orders. Intuitively, this is because if one observes a long sequence of${\displaystyle B^n}$, then one would become increasingly sure that the${\displaystyle Pr(A|B^n)\to \frac{2}{3}}$, meaning that the observable part of the system can be affected by something infinitely in the past.^[1][2]

Conversely, there exists a space of subshifts on 6 symbols, projected to subshifts on 2 symbols, such that any Markov measure on the smaller subshift has a preimage measure that is not Markov of any order (Example 2.6^[2]).

LetV be a finite set ofn symbols (alphabet). LetX denote the set⁠${\displaystyle V^{\mathbb{Z}}}$⁠ of all bi-infinite sequences of elements ofV together with theshift operatorT. We endowV with thediscrete topology andX with theproduct topology. Asymbolic flow orsubshift is aclosedT-invariant subsetY ofX^[3] and the associated languageL_Y is the set of finite subsequences ofY.^[4]

Now letA be ann ×nadjacency matrix with entries in{0, 1}. Using these elements we construct adirected graphG = (V,E) withV the set of vertices andE the set of edges containing the directed edgex →y inE if and only ifA_x,y = 1. LetY be the set of all infiniteadmissible sequences of edges, where byadmissible it is meant that the sequence is awalk of the graph, and the sequence can be either one-sided or two-sided infinite. LetT be theleft shift operator on such sequences; it plays the role of the time-evolution operator of the dynamical system. Asubshift of finite type is then defined as a pair(Y,T) obtained in this way. If the sequence extends to infinity in only one direction, it is called aone-sided subshift of finite type, and if it isbilateral, it is called atwo-sided subshift of finite type.

Formally, one may define the sequences of edges as

${\displaystyle {\mathrm{\Sigma }}_A^{+}=\left\{(x_0,x_1,\dots ):x_j\in V,A_{x_j{x}_{j+1}}=1,j\in \mathbb{N}\right\}.}$

This is the space of all sequences of symbols such that the symbolp can be followed by the symbolq only if the(p,q)-th entry of the matrixA is 1. The space of allbi-infinite sequences is defined analogously:

${\displaystyle {\mathrm{\Sigma }}_A=\left\{(\dots ,x_{-1},x_0,x_1,\dots ):x_j\in V,A_{x_j{x}_{j+1}}=1,j\in \mathbb{Z}\right\}.}$

Theshift operatorT maps a sequence in the one- or two-sided shift to another by shifting all symbols to the left, i.e.

${\displaystyle {\displaystyle (T(x){)}_j=x_{j+1}.}}$

Clearly this map is only invertible in the case of the two-sided shift.

A subshift of finite type is calledtransitive ifG isstrongly connected: there is a sequence of edges from any one vertex to any other vertex. It is precisely transitive subshifts of finite type which correspond to dynamical systems with orbits that are dense.

An important special case is thefulln-shift: it has a graph with an edge that connects every vertex to every other vertex; that is, all of the entries of the adjacency matrix are 1. The fulln-shift corresponds to theBernoulli scheme without themeasure.

By convention, the termshift is understood to refer to the fulln-shift. Asubshift is then any subspace of the full shift that is shift-invariant (that is, a subspace that is invariant under the action of the shift operator), non-empty, and closed for the product topology defined below. Some subshifts can be characterized by a transition matrix, as above; such subshifts are then called subshifts of finite type. Often, subshifts of finite type are called simplyshifts of finite type. Subshifts of finite type are also sometimes calledtopological Markov shifts.

Many chaoticdynamical systems are isomorphic to subshifts of finite type; examples include systems withtransverse homoclinic connections,diffeomorphisms ofclosed manifolds with a positivemetric entropy, theProuhet–Thue–Morse system, theChacon system (this is the first system shown to beweakly mixing but notstrongly mixing),Sturmian systems andToeplitz systems.^[5]

Asofic system is an image of a subshift of finite type where different edges of the transition graph may be mapped to the same symbol. For example, if one only watches the output from a hidden Markov chain, then the output appears to be a sofic system.^[1] It may be regarded as the set of labellings of paths through anautomaton: a subshift of finite type then corresponds to an automaton which isdeterministic.^[6] Such systems correspond toregular languages.

Context-free systems are defined analogously, and are generated byphrase structure grammars.

Arenewal system is defined to be the set of all infinite concatenations of some fixed finite collection of finite words.

Subshifts of finite type are identical to free (non-interacting) one-dimensionalPotts models (n-letter generalizations ofIsing models), with certain nearest-neighbor configurations excluded. Interacting Ising models are defined as subshifts together with a continuous function of the configuration space^{[when defined as?]} (continuous with respect to the product topology, defined below); thepartition function andHamiltonian are explicitly expressible in terms of this function.^{[clarification needed]}

Subshifts may be quantized in a certain way, leading to the idea of thequantum finite automata.

A subshift has a natural topology, derived from theproduct topology on⁠${\displaystyle V^{\mathbb{Z}},}$⁠ where

${\displaystyle V^{\mathbb{Z}}=\prod _{n\in \mathbb{Z}}V=\{x=(\dots ,x_{-1},x_0,x_1,\dots ):x_k\in V\mathrm{\forall }k\in \mathbb{Z}\}}$

andV is given thediscrete topology. A basis for the topology of⁠${\displaystyle V^{\mathbb{Z}},}$⁠ which induces the topology of the subshift, is the family ofcylinder sets

${\displaystyle C_t[a_0,\dots ,a_s]=\{x\in V^{\mathbb{Z}}:x_t=a_0,\dots ,x_{t+s}=a_s\}}$

The cylinder sets areclopen sets in⁠${\displaystyle V^{\mathbb{Z}}.}$⁠ Every open set in⁠${\displaystyle V^{\mathbb{Z}}}$⁠ is acountable union of cylinder sets. Every open set in the subshift is the intersection of an open set of⁠${\displaystyle V^{\mathbb{Z}}}$⁠ with the subshift. With respect to this topology, the shiftT is ahomeomorphism; that is, with respect to this topology, it iscontinuous with continuous inverse.

The space⁠${\displaystyle V^{\mathbb{Z}}}$⁠ is homeomorphic to aCantor set.

A variety of different metrics can be defined on a shift space. One can define a metric on a shift space by considering two points to be "close" if they have many initial symbols in common; this is thep-adic metric. In fact, both the one- and two-sided shift spaces arecompactmetric spaces.

A subshift of finite type may be endowed with any one of several differentmeasures, thus leading to ameasure-preserving dynamical system. A common object of study is theMarkov measure, which is an extension of aMarkov chain to the topology of the shift.

A Markov chain is a pair(P, π) consisting of thetransition matrix, ann ×n matrixP = (p_ij) for which allp_ij ≥ 0 and

${\displaystyle \sum _{j=1}^n{p}_{ij}=1}$

for alli. Thestationary probability vectorπ = (π_i) has allπ_i ≥ 0,$\sum {\pi }_i=1$ and has

${\displaystyle \sum _{i=1}^n{\pi }_i{p}_{ij}={\pi }_j.}$

A Markov chain, as defined above, is said to becompatible with the shift of finite type ifp_ij = 0 wheneverA_ij = 0. TheMarkov measure of a cylinder set may then be defined by

${\displaystyle \mu (C_t[a_0,\dots ,a_s])={\pi }_{a_0}{p}_{a_0,a_1}\cdots p_{a_{s-1},a_s}}$

TheKolmogorov–Sinai entropy with relation to the Markov measure is

${\displaystyle s_{\mu }=-\sum _{i=1}^n{\pi }_i\sum _{j=1}^n{p}_{ij}\log p_{ij}}$

TheArtin–Mazur zeta function is defined as theformal power series

${\displaystyle \zeta (z)=\exp \left(\sum _{n=1}^{\mathrm{\infty }}|\text{Fix}(T^n)|\frac{z^n}{n}\right),}$

whereFix(T ⁿ) is the set offixed points of then-fold shift.^[7] It has a product formula

${\displaystyle \zeta (z)=\prod _{\gamma }{\left(1-z^{|\gamma |}\right)}^{-1}}$

whereγ runs over the closed orbits.^[7] For subshifts of finite type, the zeta function is arational function ofz:^[8]

${\displaystyle \zeta (z)=(det(I-zA){)}^{-1}.}$

• Transfer operator
• De Bruijn graph
• Quantum finite automata
• Axiom A

• Brin, Michael; Stuck, Garrett (2002).Introduction to Dynamical Systems (2nd ed.).Cambridge University Press.ISBN 0-521-80841-3.
• David Damanik,Strictly Ergodic Subshifts and Associated Operators, (2005)
• Pytheas Fogg, N. (2002).Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.).Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Berlin:Springer-Verlag.ISBN 3-540-44141-7.Zbl 1014.11015.
• Natasha Jonoska,Subshifts of Finite Type, Sofic Systems and Graphs, (2000).
• Michael S. Keane,Ergodic theory and subshifts of finite type, (1991), appearing as Chapter 2 inErgodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Tim Bedford, Michael Keane and Caroline Series, Eds. Oxford University Press, Oxford (1991).ISBN 0-19-853390-X(Provides a short expository introduction, with exercises, and extensive references.)
• Lind, Douglas; Marcus, Brian (1995).An introduction to symbolic dynamics and coding.Cambridge University Press.ISBN 0-521-55124-2.Zbl 1106.37301.
• Teschl, Gerald (2012).Ordinary Differential Equations and Dynamical Systems.Providence:American Mathematical Society.ISBN 978-0-8218-8328-0.
• Xie, Huimin (1996).Grammatical Complexity and One-Dimensional Dynamical Systems. Directions in Chaos. Vol. 6. World Scientific.ISBN 9810223986.

• Williams, Susan G., ed. (2004).Symbolic Dynamics and Its Applications: American Mathematical Society, Short Course, January 4-5, 2002, San Diego, California. Proceedings of symposia in applied mathematics: AMS short course lecture notes. Vol. 60.American Mathematical Society.ISBN 0-8218-3157-7.Zbl 1052.37003.

• Ergodic theory
• Automata (computation)
• Markov processes
• Combinatorics on words
• Symbolic dynamics

• Articles with short description
• Short description matches Wikidata
• Wikipedia articles needing clarification from April 2019