The paper deals with the synchronization of a random automaton that is sampled uniformly at random from the set of all automata with n states and m letters. We show that for m = 4, the probability that a random automaton is synchronizing is larger than a positive constant. Bibliography: 9 titles.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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).
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. Mateescu and A. Salomaa, “Many-valued truth functions, Černý's conjecture and roadcoloring,” Bull. EATCS, 68, 134–150 (1999).
J.-E. Pin, “On two combinatorial problems arising from automata theory,” Ann. Discrete Math., 17, 535–548 (1983).
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).
E. Skvortsov and Yu. Zaks, “Synchronizing random automata,” Discrete Math. Theor. Comput. Sci., 12, No. 4, 95–108 (2010).
M. V. Volkov, “Synchronizing automata and the Černý conjecture,” Lect. Notes Comput. Sci., 5196, 11–27 (2008).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 402, 2012, pp. 83–90.
Rights and permissions
About this article
Cite this article
Zaks, Y.I., Skvortsov, E.S. Synchronizing random automata on a 4-letter alphabet. J Math Sci 192, 303–306 (2013). https://doi.org/10.1007/s10958-013-1396-4
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-013-1396-4