Finding DFAs with maximal shortest synchronizing word length

H. Zantema, H. Don

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

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
(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≤4
n≤4
we do the full analysis yielding 19 new DFAs with smallest synchronizing word length (n−1) 2
(n−1)2
, refuting Trahtman’s conjecture. All these new DFAs are extensions of DFAs that were known before. For n≥5
n≥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
Cn
do not admit non-trivial extensions keeping the same smallest synchronizing word length (n−1) 2
(n−1)2
.
Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings
Subtitle of host publication11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings
EditorsFrank Drewes, Carlos Martín-Vide, Bianca Truthe
Place of PublicationDordrecht
PublisherSpringer
Pages249-260
Number of pages12
ISBN (Electronic)978-3-319-53733-7
ISBN (Print)978-3-319-53732-0
DOIs
Publication statusPublished - 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10168 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Cite this

Zantema, H., & Don, H. (2017). Finding DFAs with maximal shortest synchronizing word length. In F. Drewes, C. Martín-Vide, & B. Truthe (Eds.), Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings (pp. 249-260). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10168 LNCS). Dordrecht: Springer. https://doi.org/10.1007/978-3-319-53733-7_18