• Search
•

×

### System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
No Access

# Lower Bounds for Synchronizing Word Lengths in Partial Automata

https://doi.org/10.1142/S0129054119400021Cited by:7 (Source: Crossref)

It was conjectured by Černý in 1964, that a synchronizing DFA on $n$ states always has a synchronizing word of length at most $(n−1)2$, and he gave a sequence of DFAs for which this bound is reached. Until now a full analysis of all DFAs reaching this bound was only given for $n≤5$, and with bounds on the number of symbols for $n≤12$. Here we give the full analysis for $n≤7$, without bounds on the number of symbols.

For PFAs (partial automata) on $≤7$ states we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding $(n−1)2$ for $n≥4$. Where DFAs with long synchronization typically have very few symbols, for PFAs we observe that more symbols may increase the synchronizing word length. For PFAs on $≤10$ states and two symbols we investigate all occurring synchronizing word lengths.

We give series of PFAs on two and three symbols, reaching the maximal possible length for some small values of $n$. For $n=6,7,8,9$, the construction on two symbols is the unique one reaching the maximal length. For both series the growth is faster than $(n−1)2$, although still quadratic.

Based on string rewriting, for arbitrary size we construct a PFA on three symbols with exponential shortest synchronizing word length, giving significantly better bounds than earlier exponential constructions. We give a transformation of this PFA to a PFA on two symbols keeping exponential shortest synchronizing word length, yielding a better bound than applying a similar known transformation. Both PFAs are transitive.

Finally, we show that exponential lengths are even possible with just one single undefined transition, again with transitive constructions.

Communicated by Émilie Charlier, Julien Leroy and Michel Rigo

## References

• 1. D. S. Ananichev, M. V. Volkov and V. V. Gusev , Primitive digraphs with large exponents and slowly synchronizing automata, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 402(Kombinatorika i Teoriya Grafov. IV) (2012) 9–39, p. 218. Google Scholar
• 2. J. Černý , Poznámka k homogénnym experimentom s konečnými automatmi, Matematicko-fyzikálny časopis, Slovensk. Akad. Vied 14(3) (1964) 208–216. Google Scholar
• 3. M. de Bondt, Fast algorithms for anti-distance matrices as a generalization of Boolean matrices; https://arXiv.org/abs/1705.08743 (2017). Google Scholar
• 4. M. de Bondt, Subset synchronization of DFAs and PFAs, and some other results; http://arXiv.org/abs/1807.04661 (2018). Google Scholar
• 5. M. de Bondt, H. Don and H. Zantema , DFAs and PFAs with long shortest synchronizing word length, Developments in Language Theory, eds. Charlier, É.Leroy, J.Rigo, M., Lecture Notes in Computer Science, Vol. 10396 (Springer, Cham, 2017). Crossref
• 6. M. de Bondt, H. Don and H. Zantema, Slowly synchronizing automata with fixed alphabet size, Information and Computation (preprint); https://arXiv.org/abs/1609.06853 (2017). Google Scholar
• 7. H. Don and H. Zantema , Finding DFAs with maximal shortest synchronizing word length, Language and Automata Theory and Applications, eds. Drewes, F.Martín-Vide, C.Truthe, B., Springer Lecture Notes in Computer Science, Vo. 10168 (Springer, Cham, 2017). Crossref
• 8. M. Dzyga, R. Ferens, V. V. Gusev and M. Szykuła , Attainable Values of Reset Thresholds, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), eds. K. G. LarsenH. L. BodlaenderJ.-F. Raskin, Leibniz International Proceedings in Informatics (LIPIcs) 83 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017), pp. 40:1–40:14. Google Scholar
• 9. P. Frankl , An extremal problem for two families of sets, European Journal of Combinatorics 3 (1982) 125–127. Crossref, Web of Science
• 10. B. Gerencsér, V. V. Gusev and R. M. Jungers , Primitive sets of nonnegative matrices and synchronizing automata, SIAM J. Matrix Anal. Appl. 39(1) (2018) 83–98. Crossref, Web of Science
• 11. J. Kari , A counterexample to a conjecture concerning synchronizing words in finite automata, EATCS Bulletin 73 (2001) 146–147. Google Scholar
• 12. A. Kisielewicz, J. Kowalski and M. Szykuła , Experiments with synchronizing automata, Implementation and Application of Automata, eds. Y.-S. HanK. Salomaa (Springer International Publishing, Cham, 2016), pp. 176–188. Crossref
• 13. P. V. Martyugin , Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata, Diskretn. Anal. Issled. Oper. 15(4) (2008) 44–56, 99. Google Scholar
• 14. P. V. Martyugin , A lower bound for the length of the shortest carefully synchronizing words, Russian Mathematics (Iz. VUZ) 54(1) (2010) 46–54. Crossref
• 15. P. V. Martyugin , Synchronization of automata with one undefined or ambiguous transition, Implementation and Application of Automata, eds. N. MoreiraR. Reis (Springer, Berlin, Heidelberg, 2012), pp. 278–288. Crossref
• 16. P. V. Martyugin , Careful synchronization of partial automata with restricted alphabets, Computer Science — Theory and Applications, eds. A. A. BulatovA. M. Shur (Springer, Berlin, Heidelberg, 2013), pp. 76–87. Crossref
• 17. J.-E. Pin , On two combinatorial problems arising from automata theory, Annals of Discrete Mathematics 17 (1983) 535–548. Google Scholar
• 18. A. Roman , A note on Černý conjecture for automata with 3-letter alphabet, Journal of Automata, Languages and Combinatorics 13(2) (2008) 141–143. Google Scholar
• 19. I. Rystsov , Asymptotic estimate of the length of a diagnostic word for a finite automaton, Cybernetics 16(2) (1980) 194–198. Crossref
• 20. M. Szykuła , Improving the Upper Bound on the Length of the Shortest Reset Word, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), eds. R. NiedermeierB. Vallée, Leibniz International Proceedings in Informatics (LIPIcs) 96 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018), pp. 56:1–56:13. Google Scholar
• 21. A. N. Trahtman , An efficient algorithm finds noticeable trends and examples concerning the Černý conjecture, Mathematical Foundations of Computer Science 2006: 31st International Symposium, MFCS 2006, eds. R. KrálovičP. Urzyczyn (Springer, Berlin, Heidelberg, 2006), pp. 789–800. Google Scholar
• 22. M. Volkov , Synchronizing automata and the Černý conjecture, Proceedings of LATA, Springer LNCS, Vol. 5196 (2008), pp. 11–27. Google Scholar
• 23. V. Vorel , Subset synchronization and careful synchronization of binary finite automata, Int. J. Found. Comput. Sci. 27(5) (2016) 557–578. Link, Web of Science
Remember to check out the Most Cited Articles!

Check out these Handbooks in Computer Science