Subshift of finite type (${\Sigma }_A=\{x\in \{1,\dots ,m{\}}^{\mathbb{Z}}:A_{x_k{x}_{k+1}}=1\text{ for all }k\}$)

A subshift of finite type is a closed subset of a finite-alphabet full shift defined by finitely many forbidden finite words, with the restricted left shift. After replacing symbols by sufficiently long blocks, its constraints can be described by a zero-one symbolic transition matrix. In this presentation, membership means that every consecutive pair follows an allowed transition. The resulting sequence space is a compact metric space and the restricted left shift is a homeomorphism.

A fixed point of the $n$th iteration of a map of a subshift of finite type is determined uniquely by its length-$n$ block with a permitted closing transition. Summing the counts of length-$n$ closed walks over their starting symbols gives the displayed trace. This counts points whose least period divides $n$. If $P_n$ counts points of least period exactly $n$, then $\mathrm{tr}(A^n)={\sum }_{d\mid n}{P}_d$, and Möbius inversion gives $P_n={\sum }_{d\mid n}{\mu }_{\mathrm{M}}(n/d)\mathrm{tr}(A^d)$. The number of distinct least-period-$n$ periodic orbits is $P_n/n$.

The adjacency matrix of a directed graph whose vertices are symbols and whose directed edges are the permitted consecutive pairs. Its entries indicate permission. In comparison, the transition matrix of a Markov chain records transition probabilities.

A finite word over an alphabet is locally admissible for a zero-one symbolic transition matrix if every consecutive pair is permitted. Its length counts symbols, so length $n+1$ corresponds to $n$ transitions. The number with endpoints $i,j$ is $(A^n{)}_{ij}$ by matrix multiplication. Local admissibility does not always imply occurrence in a two-sided subshift of finite type: the matrix $\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$ permits the word $(1,2)$ but admits no two-sided sequence. If every row and column has a nonzero entry, every locally admissible word extends in both directions.