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
.
(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 language | English |
|---|---|
| Title of host publication | Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings |
| Subtitle of host publication | 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings |
| Editors | Frank Drewes, Carlos Martín-Vide, Bianca Truthe |
| Place of Publication | Dordrecht |
| Publisher | Springer |
| Pages | 249-260 |
| Number of pages | 12 |
| ISBN (Electronic) | 978-3-319-53733-7 |
| ISBN (Print) | 978-3-319-53732-0 |
| DOIs | |
| Publication status | Published - 2017 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 10168 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |