Subshifts of Finite Type, Sofic Systems and Graphs

Let B be a finite set of words (blocks), each with length k (i.e. a finite set of k-blocks) in the alphabet A. We define a subshift of finite type (SFT) $\Gamma$ as:

$$\Gamma= \{\,x\in A^Z\, \vert \, \forall i\, \, x_ix_{i+1}\dots x_{i+k-1} \in B\,\}.$$

In other words, $\Gamma$ is the subshift of A^Z containing all the points for which every k-block is in B. We say that B determines $\Gamma$. Note 1.1.3 For every $m\ge k$ the SFT $\Gamma$ can be determined with a finite set of words with length m by constructing the allowable words with length m.

Every subshift of finite type can be represented as the set of all bi-infinite paths of a finite graph G=(V,E) in the following way: Let V=A^k-1 and let an edge in G go from $(a_1,a_2,\dots, a_{k-1})$ to $( a_2,a_3,\dots, a_k)$ iff $a_1\dots a_k \in B$. So, the set of edges E can be regarded as B, i.e. every edge in G is identified with an element in B. Then $x=(\dots,x_{-1},x_0,x_1,\dots)$ is an element of $\Gamma$ iff $\dots , x_{-1}\dots x_{k-2},x_0\dots x_{k-1},x_1\dots x_k, \dots$ is a bi-infinite path in G. (Note that bi-infinite paths in G can be regarded also as elements of the higher k-block system of $\Gamma$.)

Definition The subshift $S\subset A^Z$ is called a sofic system provided there is an SFT $\Gamma$ and a k-block factor map $\pi:\Gamma\rightarrow S$.

Two factor maps $\pi_1:\Gamma_1\rightarrow S_1$ and $\pi_2:\Gamma_2\rightarrow S_2$ are conjugate if there are topological conjugacies f,g such that $\pi_2 f=g\pi_1$.

We can easily see that every k-block factor map $\pi$ from a SFT $\Gamma$ to a sofic system S is conjugate to a one-block factor map. Let $\pi:\Gamma\rightarrow S$ be a k-block factor map generated by $\pi_*:A^k\rightarrow A$. Let $\Gamma'$ be the higher k-block system of $\Gamma$, and $\pi':\Gamma' \rightarrow S$ be the one-block factor map generated with $(x_1,\dots,x_k)\mapsto \pi_*(x_1,\dots,x_k)$. Then $\pi'\phi=id_S \pi$.

Let $\Gamma$ be an SFT determined by a finite set of words with length m and $\pi:\Gamma\rightarrow S$ be an n-block factor map. By note 1.1.2 and note 1.1.3, we can take that $\pi$ is a k-block factor map and $\Gamma$ is determined by a set of words with length k where $k=\mbox {max} \{ m, n \}$. Let G=(V,E) be the finite graph representing the SFT $\Gamma$ as above. We saw that G also represents the higher k-block system $\Gamma'$. The factor map $\pi$ can be represented on the graph G by a labeling function $\lambda:E \rightarrow A$, i.e. $\lambda(x_1\dots x_k)=\pi_* (x_1,\dots,x_k)$. In this case elements of the sofic system S are the labels of all bi-infinite paths of G. So, $\Gamma$, S and the factor map $\pi:\Gamma\rightarrow S$ are represented by the graph $G=(V,E,\lambda)$. We can go the opposite way too. Assume that $G=(V,E,\lambda)$ is a finite graph with vertices V, edges E and a labeling function $\lambda:E \rightarrow A$. We define two functions: source $s:E\rightarrow V$ and target $t:E\rightarrow V$ representing the source and the target of an edge. Suppose that every vertex in G lies on a bi-infinite path. That means that for every vertex $v\in V$ there are two edges e₁, e₂ such that t(e₁)=s(e₂)=v. If there are vertices in G that don't have that property, we will delete them (together with the edges) from G. We iterate this process of deleting vertices and edges until every remaining vertex in G has an edge coming in and an edge going out.

Then

$$\Gamma=\Gamma(G)=\{\, x\in E^{Z}\,\vert\, x \mbox { is a bi-infinite path in } G\,\}$$

is a subshift of finite type on the alphabet E defined with a two-block set $\{x_ix_{i+1}\vert$
$\, t(x_i)=s(x_{i+1}) \,\}$. The labeling function $\lambda$ generates a one-block factor map $\pi:\Gamma\rightarrow S$ where S=S(G) is the sofic system equal to the set of labels of all bi-infinite paths in G. We will call $\Gamma=\Gamma(G)$ the cover of S=S(G) given with the graph G.

Since every SFT is also a sofic system (the identity map is a one-block factor map), we have that every sofic system can be represented with a finite labeled graph (having every vertex lying on a bi-infinite path), and every such graph represents a sofic system. We will call these graphs sofic acceptors (SA) and will refer to them as to representations of sofic systems.