Synchronizing Graphs

Definition A sofic acceptor $G=(V,E,\lambda)$ is called synchronizing if for every vertex $v\in V$ there is a word $x_v\in L(G)$ such that for every path p in G,

$$\lambda(p) = x_v \,\,\, \Rightarrow\,\,t(p)=v.$$

The word x_v is called a synchronizing word for v.

In other words, x_v is a synchronizing word for v if every path in G with label x_v ends at v.

A strongly connected component C with a set of vertices W of a SA $G=(V,E,\lambda)$ is called initial if for every vertex w in C and every vertex $v\in V$, if there is a path from v to w then $v\in W$.

Proposition 2.1.1 If G is a synchronizing SA then every initial component of G recognizes a maximal FTR language in L(G).

proof: Let $C_0=(V_0,E_0,\lambda_0)$ be an initial component of a SA G. Let L₀=L(C₀). Then L₀ is an FTR language and if $v\in V_0$ there is a synchronizing word x_v for v which is also in L₀. Let L₁ be a maximal FTR language such that $L_0\subset L_1$ (it exists by corollary 1.2.3). By proposition 1.2.2, there is a strongly connected component C₁ of G such that L(C₁)=L₁. But $x_v\in L_1$, so v is a vertex in C₁ and C₁=C, i.e. L₀=L₁. $\Box$

The SFT represented on figure 1.1 has a synchronizing representation. The first representation (a) is synchronizing: aa is a synchronizing word for the vertex 1, aab is synchronizing for 2, c is synchronizing for 3 and cb is synchronizing for the vertex 4. The second representation (b) on the same figure is not synchronizing since the vertices in the initial component don't have synchronizing words. (Note that this component recognizes a maximal FTR language, so the converse of the proposition 2.1.1 does not hold.) The same SFT is represented non-deterministicly on figure 1.2. That representation is also synchronizing.

Looking at this example, we see that a sofic system does not have a unique homomorphicly minimal synchronizing representation. Assume that the SFT represented in figure 1.1 has a unique homomorphicly minimal representation G. That representation must have three vertices, since there is a synchronizing representation of the same SFT with three vertices and there is no representation with two vertices. Then there must be an onto homomorphism f from the synchronizing deterministic representation (figure 1.1) to G. This means that f(v₁)=f(v₂) for some $v_1,v_2\in \{1,2,3,4\}$ $(v_1\ne v_2)$. But for any choice of v₁ and v₂, collapsing v₁ and v₂ would lead to a representation of a different sofic system.

Let G₁ and G₂ be two representations of a sofic system S. If $\Phi:G_1 \rightarrow G_2$ is an onto graph homomorphism we will write $G_2\preceq G_1$. We write $G_1\equiv G_2$ if $\Phi$ is both 1-1 and onto homomorphism. In that case we will consider G₁ and G₂ as equal, i.e. modulo $\equiv$, $\preceq$ is a partial ordering. Equivalently, if $\Gamma_1$ and $\Gamma_2$ are the covers given with G₁ and G₂ respectively, $\phi:\Gamma_1 \rightarrow\Gamma_2$ is a one-block factor map determined with $\Phi$ and we will write $\Gamma_2 \preceq\Gamma_1$. $\Gamma_1 \equiv \Gamma_2$ if $\Gamma_1$ is topologicaly conjugate to $\Gamma_2$ via a one-block factor map. Let $\cal{ C}$ be a collection of representations of a sofic system S. The representation G in $\cal{ C}$ is $\cal{ C}$-minimal if for every representation G' in $\cal{ C}$, $G'\preceq G \,\, \Rightarrow\,\,G'\equiv G$. If for every G' in $\cal{ C}$, $G\preceq G'$ then we say that G is a unique $\cal{ C}$-minimal element of $\cal{ C}$. Let $\cal {D}\cal {R}(S)$ be the class of all deterministic representations of a sofic system S, and $\cal {S} \cal {R}(S)$ be the class of all synchronizing representations of S. Considering the example on figure 1.1, we conclude: Proposition 2.1.2 There is a sofic system S such that (i) $\cal {D}\cal {R}(S)$ has no unique $\cal {D}\cal {R}$-minimal element (ii) $\cal {S} \cal {R}(S)$ has no unique $\cal {S} \cal {R}$-minimal element Theorem 1.1.5 refers to the class of irreducible deterministic representations of an irreducible sofic system. By that theorem, this class has a unique minimal element. So the example above shows that we can not extend the theorem 1.1.5 to the class $\cal {D}\cal {R}$ or the class $\cal {S} \cal {R}$ of sofic systems even for subshifts of finite type. This motivates us to investigate the synchronizing deterministic representations of sofic systems. We will call this class of representations $\cal {S}\cal {D}\cal {R}$. We end this section with the following proposition: Proposition 2.1.3 Let G be an SA and G' be the reduced SA of G. If G is synchronizing then so is G'. proof: If x_v is a synchronizing word for v, then every path in G' labeled x_v must end at [v]. $\Box$