Some notes on the classification of shift spaces: shifts of finite type; sofic shifts; and finitely defined shifts (Q2160339)

A \textit{subshift} is a closed subspace of \(A^{\mathbb N}\) or \(A^{\mathbb Z}\) that is invariant under the shift \((a_i)_i\mapsto(a_{i+1})_i\). Equivalently, it is a subspace defined by a collection of \textit{excluded patterns} \(F\). Important classes of subshifts include \textit{subshifts of finite type} and \textit{sofic shifts}; if the alphabet \(A\) is finite then there are numerous equivalent formulations of these definitions, but the present article advises for caution if \(A\) is infinite, and states what the ``correct'' definition should be. Subshifts of finite type appear in Definition~5.1. For this, let us be more precise: write \(\mathbb M\) for a monoid, typically \(\mathbb N\) or \(\mathbb Z\), and \(\mathcal N=\bigcup_{\text{finite }N\subset\mathbb M}A^N\); a set of forbidden patterns is \(F\subseteq\mathcal N\), and the associated shift is the set of sequences in \(A^{\mathbb M}\) none of whose translates restrict to an element of \(F\). A \textit{subshift of finite type} is then a subshift defined by a set of excluded patterns contained in \(A^N\) for some finite \(N\). (This is more general than the naive definition requiring \(F\) to be finite.) Sofic shifts appear in Definition~6.2. They may be defined as quotients of a subshift of finite type by a ``locally bounded finite-to-one sliding block code'', namely, as the images of a subshift of finite type \(\Omega\subseteq B^{\mathbb M}\) by a uniformly continuous, \(\mathbb M\)-equivariant map \(E\colon\Omega\to A^{\mathbb M}\) such that \(E^{-1}(\{a\}\times A^{\mathbb M\setminus\{1\}})\) is a union of at most \(k\) cylinders, for all \(a\in A\). Presumably (though I have not been able to locate this in the text) this is equivalent, by increasing \(B\), to being the image of \(\Omega\) by a uniformly bounded-to-\(1\) map \(B\to A\). The text derives then various characterizations and properties of subshifts and sliding block codes, using the above definitions and relating them to the more concrete setting of \(\mathbb M=\mathbb N\) or \(\mathbb Z\) and finite \(A\), when subshifts of finite type may be viewed as spaces of paths in a vertex-labelled graph and sofic shifts as spaces of paths in an edge-labelled graph.