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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. L. Adler, L. W. Goodwyn, and B. Weiss, “Equivalence of topological Markov shifts,” Israel J. Math., 27, 49–63 (1977).
M. Almeida, N. Moreira, and R. Reis, “Enumeration and generation with a string automata representation,” Theoret. Comput. Sci., 387, 93–102 (2007).
D. S. Ananichev, V. V. Gusev, and M. V. Volkov, “Slowly synchronizing automata and digraphs,” Lect. Notes Comput. Sci., 6281, 55–64 (2010).
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).
M. Berlinkov, “Approximating the minimum length of synchronizing words is hard,” Lect. Notes Comput. Sci., 6072, 37–47 (2010).
M. Berlinkov, “On a conjecture by Carpi and D'Alessandro,” Internat. J. Found. Comput. Sci., 22, 1565–1576 (2011).
R. Brualdi and H. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, Cambridge (1991).
A. Carpi and F. D'Alessandro, “On the hybrid Černý–road coloring problem and Hamiltonian paths,” Lect. Notes Comput. Sci., 6224, 124–135 (2010).
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).
A. L. Dulmage and N. S. Mendelsohn, “The exponent of a primitive matrix,” Canad. Math. Bull., 5, 241–244 (1962).
A. L. Dulmage and N. S. Mendelsohn, “Gaps in the exponent set of primitive matrices,” Illinois J. Math., 8, 642–656 (1964).
V. Gusev, “Lower bounds for the length of reset words in Eulerian automata,” Lect. Notes Comput. Sci., 6945, 180–190 (2011).
J. Kari, “A counter example to a conjecture concerning synchronizing words in finite automata,” Bull. Eur. Assoc. Theoret. Comput. Sci., 73, 146 (2001).
V. A. Liskovets, “The number of connected initial automata,” Kibernetika, No. 3, 16–19 (1969).
J. Olschewski and M. Ummels, “The complexity of finding reset words in finite automata,” Lect. Notes Comput. Sci., 6281, 568–579 (2010).
J.-E. Pin, “On two combinatorial problems arising from automata theory,” Ann. Discrete Math., 17, 535–548 (1983).
J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem, Oxford Univ. Press, Oxford (2005).
V. N. Sachkov and V. E. Tarakanov, Combinatorics of Nonnegative Matrices, Amer. Math. Soc., Providence, Rhode Island (2002).
S. Sandberg, “Homing and synchronizing sequences,” Lect. Notes Comput. Sci., 3472, 5–33 (2005).
E. Skvortsov and E. Tipikin, “Experimental study of the shortest reset word of random automata,”Lect. Notes Comput. Sci., 6807, 290–298 (2011).
B. Steinberg, “The Černý conjecture for one-cluster automata with prime length cycle,” Theoret. Comput. Sci., 412, 5487–5491 (2011).
A. N. Trahtman, “An efficient algorithm finds noticeable trends and examples concerning the Černý conjecture,” Lect. Notes Comput. Sci., 4162, 789–800 (2006).
A. N. Trahtman, “Notable trends concerning the synchronization of graphs and automata,” Electron. Notes Discrete Math., 25, 173–175 (2006).
A. N. Trahtman, “The road coloring problem,” Israel J. Math., 172, 51–60 (2009).
A. N. Trahtman, “Modifying the upper bound on the length of minimal synchronizing word,” Lect. Notes Comput. Sci, 6914, 173–180 (2011).
M. V. Volkov, “Synchronizing automata and the Černý conjecture,” Lect. Notes Comput. Sci., 5196, 11–27 (2008).
M. V. Volkov, “Synchronizing automata preserving a chain of partial orders,” Theoret. Comput. Sci., 410, 3513–3519 (2009).
H. Wielandt, “Unzerlegbare, nicht negative Matrizen,” Math. Z., 52, 642–648 (1950).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 402, 2012, pp. 9–39.
Rights 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
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-013-1392-8