Nonwandering sofic systems

Definition An FPR language $L\subset A^*$ is called nonwandering if for every $x\in L$ there is a word y such that $xyx\in L$. A sofic system S is called nonwandering if F(S) is nonwandering. Note 2.3.8 If L is nonwandering, for every $x\in L$ and every $k\ge 0$ there is $y\in L$ such that x is a factor of y k times. In this section we will show that each nonwandering sofic system has an SDR. We suspect that the following theorem is a known result. Theorem 2.3.9: Every nonwandering sofic system can be represented with a graph containing only nonconnected irreducible components. proof: Let G be a representation of a nonwandering sofic system S. We will construct a representation G' of S that contains only not connected irreducible components, i.e. if C₁ and C₂ are two different irreducible components in G' then they are not connected. Let K be the set of words x in F(S) such that there are vertices v,w in G that don't belong to the same irreducible component and vx=w. We will show that for every word $x\in K$ there is an irreducible component C_x of G such that $x\in L(C_x)$. Let $x\in K$. The set $H=\{\,(v,w)\,\vert\,vx=w,\,\,v \mbox{ and } w$ don't belong to the same irreducible component $\}$ is finite. Let k be the cardinality of H. By the note 2.3.8 there is a word y in F(S) that has x as a factor more than k times. If C₁ and C₂ are two irreducible components of G and there is a path from C₁ to C₂, then there is no path from C₂ to C₁. So for every $(v,w)\in H$ a path with label y can not go twice through both vertices v and w. Thus there must be two vertices v₁ and v₂ belonging to the same irreducible component and v₁x=v₂ i.e. there is an irreducible component C_x such that $x\in L(C_x)$. Construct G' from G by erasing every edge e that has the property that s(e) and t(e) belong to different components. By the above argument we have that L(G)=L(G') and G' is a representation that contains only non-connected irreducible components. $\Box$ Lemma 2.3.10 Let L₁, L₂, L₃ be FTR languages. If $L_1\subset L_2\cup L_3$ then $L_1\subset L_2$ or $L_1\subset L_3$. proof: Assume that $x_2\in L_1- L_3$ and $x_3\in L_1 - L_2$. Since L₁ is an FTR language, there is y such that $x_2yx_3\in L_1$, i.e. $x_2yx_3 \in L_2\cup L_3$ i.e. $x_3\in L_2$ or $x_2\in L_3$, which is contradiction with our assumption. Thus $L_1-L_2=\emptyset$ or $L_1-L_3=\emptyset$. $\Box$ Note 2.3.11 It can be proved, similarly to the lemma 2.3.10, that if an FTR L is a subset of a union of a finite collection of FTR languages than there is an FTR language in that collection that contains L entirely. Theorem 2.3.12 For every non-wandering sofic system S there is a synchronizing deterministic representation. proof: Let G be a representation of S that contains only non-connected irreducible components (G exists by the theorem 2.3.9). Let G' be a representation of S obtained by erasing every irreducible component of G that recognizes an FTR which is not maximal. Then L(G')=L(G)=F(S) and by lemma 2.3.10 (and note 2.3.11) irreducible components of G' recognize different maximal FTR languages i.e. for every irreducible component C of G' there is a word x_C such that $x_C \in L(C)$ but $x_C\not \in F(S)-L(C)$. By lemma 2.3.5 every maximal FTR language in F(S) has an irreducible SDR. Let G'' be representation obtained from G' such that for every maximal FTR L₀ in F(S), the irreducible component of G' that recognizes L₀ is substituted with the irreducible SDR of L₀. We show that G'' is synchronizing: Let v be a vertex in G'' and C the irreducible component containing v. Let x_v be the synchronizing word for v in C. Since L(C) is an FTR language, there is y such that $z=x_Cyx_v\in L(C)$. Then z is synchronizing for v for the entire G''. $\Box$ Theorem 2.3.12 shows that non-wandering sofic systems have synchronizing deterministic representations and so non-wandering sofic systems have unique $\cal {S}\cal {D}\cal {R}$-minimal representation.