Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Finding DFAs with Maximal Shortest Synchronizing Word Length
verfasst von : Henk Don, Hans Zantema
Erschienen in: Language and Automata Theory and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
It was conjectured by Černý in 1964 that a synchronizing DFA on n states always has a shortest synchronizing word of length at most \((n-1)^2\), and he gave a sequence of DFAs for which this bound is reached. In 2006 Trahtman conjectured that apart from Černý’s sequence only 8 DFAs exist attaining the bound. He gave an investigation of all DFAs up to certain size for which the bound is reached, and which do not contain other synchronizing DFAs. Here we extend this analysis in two ways: we drop this latter condition, and we drop limits on alphabet size. For \(n \le 4\) we do the full analysis yielding 19 new DFAs with smallest synchronizing word length \((n-1)^2\), refuting Trahtman’s conjecture. All these new DFAs are extensions of DFAs that were known before. For \(n \ge 5\) we prove that none of the DFAs in Trahtman’s analysis can be extended similarly. In particular, as a main result we prove that the Černý examples \(C_n\) do not admit non-trivial extensions keeping the same smallest synchronizing word length \((n-1)^2\).