Minimal Number of Vertices of SDR's

The concept of a minimal representation with respect to the relation $\preceq$ is natural and canonical, but one can also consider minimal representations in terms of number of vertices, i.e. a representation is minimal if it has the minimum number of vertices. In that sense, considering the example on figure 1.1. there is a sofic system with no unique minimal deterministic representation. By the same example we see that the minimal synchronizing deterministic representation is not minimal in terms of number of vertices, since there is a representation with three vertices (figure 1.2). In this section we will see a condition when the minimal synchronizing deterministic representation of a sofic system is also minimal in terms of the number of states. That condition will be given using the concept of right context of a vertex. Let $R_1,\dots ,R_k\subset A^*$ and let $\cal{ R}=\{\,R_1,\dots, R_k\,\}$. A finite set of words $X=\{\,x_1,\dots,x_k\,\}$ is a good set for $\cal{R}$ if for every $R\in \cal{R}$ there is $x_R\in X$ such that $x_R\in R$ and for every i,j $(i\ne j)$ such that $1\le i\, ,j\le k$, $\{\,x_{R_i}\, ,x_{R_j}\,\}\not \subset R_i\cap R_j$. One obvious case when $\cal{R}$ doesn't have a good set is when there is R_i and $I=\{\,i_1,\dots, i_s\,\}$ such that $i\not \in I$ and

$$R_i=\bigcup\limits_{j\in I} R_{j} \qquad\qquad\qquad {*}$$

Another clear case when $\cal{R}$ always has a good set is when for every $i=1,\dots,k$

$$R_i\not \subset \bigcup\limits_{j\not = i} R_j \qquad\qquad\qquad {**}$$

The condition (**) is only sufficient for $\cal{R}$ to have a good set, but it is not necessary. Also, the condition (*) is only sufficient for $\cal{R}$ not to have a good set. The question remains what is the necessary and sufficient condition for $\cal{R}$ to have a good set. Theorem 2.4.1 Let $G=(V,E,\lambda)$ be an SDR for a sofic system S and $\cal{R}=\{\,R(v)\,\vert\,v\in V\,\}$. If R has a good set then G has a minimal number of vertices i.e. if $G'=(V',E',\lambda')$ is another representation of S then $\vert V\vert\le \vert V'\vert$. Moreover, if |V|=|V'| then $G \equiv G'$. proof: Let G' be another representation of S and X be a good set for $\cal{R}$. For a vertex $v\in V$ we can choose a synchronizing word m_v and a word $x_v\in X$ such that $x_v\in R(v)$. Then $m_vx_v\in F(S)$. There is a path p=p₁p₂ in G' with $\lambda' (p)=m_vx_v$, $\lambda' (p_1)=m_v$ and $\lambda'(p_2)=x_v$. Let w_v=t(p₁)=s(p₂). Define $f:V\rightarrow V'$ with f(v)=w_v. We show that f is an injection. Assume f(v₁)=f(v₂), so w_v1=w_v2. Then $m_{v_1}x_{v_2},m_{v_2}x_{v_1} \in F(S)$, i.e. $\{\,x_{v_1},\,x_{v_2}\,\} \in R(v_1)\cap R(v_2)$ which is the contradiction to the property of a good set. Let |V|=|V'|. The argument above also shows that every synchronizing word m_v for a vertex $v\in V$ is also synchronizing for $f(v)\in V'$. So, the function f is a bijection and G' is synchronizing. We see that G' is deterministic too. Let e₁,e₂ be two edges in V' such that s(e₁)=s(e₂)=f(v) and $\lambda'(e_1)=\lambda'(e_2)=a$. Then m_va is synchronizing for va in G. So m_va is synchronizing for f(va) in G'. If p is a path in G' with label m_va then t(p)=f(va)=t(e₁)=t(e₂), i.e. e₁=e₂. By theorem 2.2.5, G and G' are isomorphic. $\Box$ Proposition 2.4.2 Let $G=(V,E,\lambda)$ be a sofic acceptor and suppose $\cal{R}=\{\,R(v)\,\vert\,v\in V\,\}$ satisfies (*). Then there is a sofic acceptor $G'=(V',E',\lambda')$ representing the same sofic system and |V'|< |V|. proof: Let $W\subset V$ and $v\in V-W$ such that $R(v)=\bigcup \limits _{w\in W} R(w)$. We construct $G'=(V',E',\lambda')$ from G in the following way: $V'=V-\{v\}$, we erase every edge e with t(e)=v and we add edges e_w for every $w\in W$ such that s(e_w)=s(e), t(e_w)=w and $\lambda'(e_w)=\lambda(e)$. We also erase every edge with source v. With this construction L(G)=L(G'). If G' is not a sofic acceptor, then we trim G' by iterating the process of erasing every vertex that doesn't have an edge coming in and an edge going out. Since L(G)=L(G') is an FPR language, trimming G' doesn't change the language. $\Box$ The theorem 2.4.1 gives only a sufficient condition when an SDR G has also a minimal number of vertices. We hope that this condition is both sufficient and necessary. We believe that finding a necessary and sufficient condition for a collection $\cal{R}$ to have a good set will be very helpful in solving the problem when an SDR has a minimal number of vertices. We end this section with a note that the collection of left contexts $\cal{L}=\{\,L(v)\,\vert\,v\in V\,\}$ of the set of vertices V of an sdr satisfies (**). So $\cal{L}$ has a good set. The good set can be chosen by choosing one synchronizing word for every vertex. A direct consequence of theorem 2.4.1 is the following proposition: Corollary 2.4.3 Let G be a representation of a sofic system such that both $\cal{L}$ and $\cal{R}$ have a good set, then G is a representation with a minimal number of vertices. proof: The proof is similar to the proof of theorem 2.4.1 $\Box$