World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

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.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Lower Bounds for Synchronizing Word Lengths in Partial Automata

    https://doi.org/10.1142/S0129054119400021Cited by:7 (Source: Crossref)
    This article is part of the issue:

    It was conjectured by Černý in 1964, that a synchronizing DFA on n states always has a synchronizing word of length at most (n1)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 n5, and with bounds on the number of symbols for n12. Here we give the full analysis for n7, 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 (n1)2 for n4. 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 (n1)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). CrossrefGoogle Scholar
    • 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). CrossrefGoogle Scholar
    • 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 ScienceGoogle Scholar
    • 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 ScienceGoogle Scholar
    • 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. CrossrefGoogle Scholar
    • 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. CrossrefGoogle Scholar
    • 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. CrossrefGoogle Scholar
    • 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. CrossrefGoogle Scholar
    • 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. CrossrefGoogle Scholar
    • 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 ScienceGoogle Scholar
    Remember to check out the Most Cited Articles!

    Check out these Handbooks in Computer Science