On synchronizing unambiguous automata (Q1116340): Difference between revisions

An unambiguous automaton C is a quadruple \((A,Q,\phi,q_ 1)\) where A is a finite alphabet, Q is a finite set of states, \(\phi\) is a monoid homomorphism from \(A^*\) into the monoid of all (0,1)-matrices of type \(Q\times Q\), and \(q_ 1\) is a both initial and final state of the automaton C. The rank of a (0,1)-matrix M of type \(k\times k\) is the smallest r such that \(M=A B\) where A, B are (0,1)-matrices of types \(k\times r\) and \(r\times k\). An automaton C is called complete if \(\phi\) (v) is not-null matrix for every \(v\in A^*\) and for every pair p, r of states there exists \(v\in A^*\) with \(\phi (v)_{p,r}=1.\) It is shown that for an unambiguous complete automaton C with n states, if \(r_ 0=\min \{rank \phi (v)\); \(v\in A^*\}\) then there exists a word \(w\in A^*\) such that \(| w| \leq r_ 0n(n-1)^ 2+(2r_ 0-1)(n- 1)\) and rank \(\phi\) (w)\(=r_ 0\). In particular, w is a synchronizing word if rank \(\phi\) (w)\(=1\). If C has a synchronizing word then there exists a synchronizing word \(w\in A^*\) of C with \(| w| \leq n^{3/2}-n^ 2+3^{n/2}-1.\) A consequence for maximal rational codes is derived.