Skip to main content
SpringerLink
Log in

Primitive digraphs with large exponents and slowly synchronizing automata

  • Published:
Journal of Mathematical Sciences Aims and scope Submit manuscript

We present several infinite series of synchronozing automata for which the minimum length of reset words is close to the square of the number of states. All these automata are tightly related to primitive digraphs with large exponents. Bibliography: 28 titles.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. R. L. Adler, L. W. Goodwyn, and B. Weiss, “Equivalence of topological Markov shifts,” Israel J. Math., 27, 49–63 (1977).

    Article  MathSciNet  MATH  Google Scholar 

  2. M. Almeida, N. Moreira, and R. Reis, “Enumeration and generation with a string automata representation,” Theoret. Comput. Sci., 387, 93–102 (2007).

    Article  MathSciNet  MATH  Google Scholar 

  3. D. S. Ananichev, V. V. Gusev, and M. V. Volkov, “Slowly synchronizing automata and digraphs,” Lect. Notes Comput. Sci., 6281, 55–64 (2010).

    Article  MathSciNet  Google Scholar 

  4. D. S. Ananichev, M. V. Volkov, and Yu. I. Zaks, “Synchronizing automata with a letter of deficiency 2,” Theoret. Comput. Sci., 376, 30–41 (2007).

    Article  MathSciNet  MATH  Google Scholar 

  5. M. Berlinkov, “Approximating the minimum length of synchronizing words is hard,” Lect. Notes Comput. Sci., 6072, 37–47 (2010).

    Article  Google Scholar 

  6. M. Berlinkov, “On a conjecture by Carpi and D'Alessandro,” Internat. J. Found. Comput. Sci., 22, 1565–1576 (2011).

    Article  MathSciNet  MATH  Google Scholar 

  7. R. Brualdi and H. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, Cambridge (1991).

    Book  MATH  Google Scholar 

  8. A. Carpi and F. D'Alessandro, “On the hybrid Černý–road coloring problem and Hamiltonian paths,” Lect. Notes Comput. Sci., 6224, 124–135 (2010).

    Article  MathSciNet  Google Scholar 

  9. J. Černý, “Poznámka k homogénnym eksperimentom s konečnými automatami,” Matematicko-fyzikalny Časopis Slovensk. Akad. Vied”, 14, No. 3, 208–216 (1964).

    MATH  Google Scholar 

  10. A. L. Dulmage and N. S. Mendelsohn, “The exponent of a primitive matrix,” Canad. Math. Bull., 5, 241–244 (1962).

    Article  MathSciNet  MATH  Google Scholar 

  11. A. L. Dulmage and N. S. Mendelsohn, “Gaps in the exponent set of primitive matrices,” Illinois J. Math., 8, 642–656 (1964).

    MathSciNet  MATH  Google Scholar 

  12. V. Gusev, “Lower bounds for the length of reset words in Eulerian automata,” Lect. Notes Comput. Sci., 6945, 180–190 (2011).

    Article  Google Scholar 

  13. J. Kari, “A counter example to a conjecture concerning synchronizing words in finite automata,” Bull. Eur. Assoc. Theoret. Comput. Sci., 73, 146 (2001).

    MathSciNet  MATH  Google Scholar 

  14. V. A. Liskovets, “The number of connected initial automata,” Kibernetika, No. 3, 16–19 (1969).

  15. J. Olschewski and M. Ummels, “The complexity of finding reset words in finite automata,” Lect. Notes Comput. Sci., 6281, 568–579 (2010).

    Article  MathSciNet  Google Scholar 

  16. J.-E. Pin, “On two combinatorial problems arising from automata theory,” Ann. Discrete Math., 17, 535–548 (1983).

    MATH  Google Scholar 

  17. J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem, Oxford Univ. Press, Oxford (2005).

    Book  MATH  Google Scholar 

  18. V. N. Sachkov and V. E. Tarakanov, Combinatorics of Nonnegative Matrices, Amer. Math. Soc., Providence, Rhode Island (2002).

  19. S. Sandberg, “Homing and synchronizing sequences,” Lect. Notes Comput. Sci., 3472, 5–33 (2005).

    Article  Google Scholar 

  20. E. Skvortsov and E. Tipikin, “Experimental study of the shortest reset word of random automata,”Lect. Notes Comput. Sci., 6807, 290–298 (2011).

    Article  MathSciNet  Google Scholar 

  21. B. Steinberg, “The Černý conjecture for one-cluster automata with prime length cycle,” Theoret. Comput. Sci., 412, 5487–5491 (2011).

    Article  MathSciNet  MATH  Google Scholar 

  22. A. N. Trahtman, “An efficient algorithm finds noticeable trends and examples concerning the Černý conjecture,” Lect. Notes Comput. Sci., 4162, 789–800 (2006).

    Article  MathSciNet  Google Scholar 

  23. A. N. Trahtman, “Notable trends concerning the synchronization of graphs and automata,” Electron. Notes Discrete Math., 25, 173–175 (2006).

    Article  MathSciNet  MATH  Google Scholar 

  24. A. N. Trahtman, “The road coloring problem,” Israel J. Math., 172, 51–60 (2009).

    Article  MathSciNet  MATH  Google Scholar 

  25. A. N. Trahtman, “Modifying the upper bound on the length of minimal synchronizing word,” Lect. Notes Comput. Sci, 6914, 173–180 (2011).

    Article  MathSciNet  Google Scholar 

  26. M. V. Volkov, “Synchronizing automata and the Černý conjecture,” Lect. Notes Comput. Sci., 5196, 11–27 (2008).

    Article  Google Scholar 

  27. M. V. Volkov, “Synchronizing automata preserving a chain of partial orders,” Theoret. Comput. Sci., 410, 3513–3519 (2009).

    Article  MathSciNet  MATH  Google Scholar 

  28. H. Wielandt, “Unzerlegbare, nicht negative Matrizen,” Math. Z., 52, 642–648 (1950).

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics and Computer Science, Ural Federal University, Ekaterinburg, Russia

    D. S. Ananichev, M. V. Volkov & V. V. Gusev

Authors
  1. D. S. Ananichev
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. V. Volkov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. V. V. Gusev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to D. S. Ananichev.

Additional information

Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 402, 2012, pp. 9–39.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ananichev, D.S., Volkov, M.V. & Gusev, V.V. Primitive digraphs with large exponents and slowly synchronizing automata. J Math Sci 192, 263–278 (2013). https://doi.org/10.1007/s10958-013-1392-8

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10958-013-1392-8

Search

Navigation