Strongly connected synchronizing automata and the language of minimal reset words (Q1637601): Difference between revisions

Černý's conjecture states that an \(n\)-state deterministic automaton for which there exists a (synchronizing) word that sends all states to a single state admits such a word of length at most \((n-1)^2\). The present paper is part of the author's algebraic approach to the conjecture along the lines of his previous joint paper with \textit{R. Reis} [Theor. Comput. Sci. 653, 97--107 (2016; Zbl 1453.68101)], providing the solution of one of the problems proposed in that paper and a partial solution of another. The algebraic formulation of the conjecture consists in considering the ideal \(I\) of all synchronizing words and showing that the state complexity of \(I\), as a regular language, is at least the square root of the minimum length of its members plus one. This suggests investigating (possibly infinite) automata having a given ideal \(I\) as the set of synchronizing words, or equivalently, its so-called reset left decompositions. The latter are partitions \(\mathcal I\) of \(I\) into left ideals such that the following properties hold: (i) For every \(a\in\Sigma\) and \(J\in\mathcal I\), there exists \(K\in\mathcal I\) such that \(Ja\subseteq K\); (ii) If \(u\in\Sigma^*\) is such that \(Iu\subseteq J\) for some \(J\in\mathcal I\), then \(u\in I\). The first main result in the paper gives sort of a universal such decomposition of any ideal of \(\Sigma^*\) in the sense that the corresponding automaton covers every automaton that has the same ideal as the set of synchronizing words. In case the ideal \(I\) is a regular language and \(\Sigma\) has \(k\geq2\) letters, the second main result gives an effective construction of a concrete finite reset left decomposition of \(I\). An application of this result gives a construction of a finite automaton with \(I\) as the set of synchronizing words with at most \((km^k)2^{km^kn}\) states, where \(m\) is twice the minimum length of words in \(I\) and \(n\) is the state complexity of \(I\); the time complexity of the algorithm is bounded by \(k\) times the number of states of the resulting automaton.