Geodesic
Synchronizing random automata on $4$-letter alphabet
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 83-90 
Yu. I. Zaks; E. S. Skvortsov. Synchronizing random automata on $4$-letter alphabet. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 83-90. http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a5/
@article{ZNSL_2012_402_a5,
     author = {Yu. I. Zaks and E. S. Skvortsov},
     title = {Synchronizing random automata on $4$-letter alphabet},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {83--90},
     year = {2012},
     volume = {402},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a5/}
}
TY  - JOUR
AU  - Yu. I. Zaks
AU  - E. S. Skvortsov
TI  - Synchronizing random automata on $4$-letter alphabet
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 83
EP  - 90
VL  - 402
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a5/
LA  - ru
ID  - ZNSL_2012_402_a5
ER  - 
%0 Journal Article
%A Yu. I. Zaks
%A E. S. Skvortsov
%T Synchronizing random automata on $4$-letter alphabet
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 83-90
%V 402
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a5/
%G ru
%F ZNSL_2012_402_a5

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

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.

[1] D. S. Ananichev, V. V. Gusev, M. V. Volkov, “Slowly synchronizing automata and digraphs”, Math. Found. Comput. Sci., Lect. Notes Comput. Sci., 6281, 2010, 55–64 | DOI | MR

[2] D. S. Ananichev, M. V. Volkov, Yu. I. Zaks, “Synchronizing automata with a letter of deficiency 2”, Theor. Comput. Sci., 376 (2007), 30–41 | DOI | MR | Zbl

[3] J. Černý, “Poznámka k homogénnym eksperimentom s konečnými automatami”, Matematicko-fyzikalny Časopis Slovensk. Akad. Vied, 14:3 (1964), 208–216 (in Slovak) | MR | Zbl

[4] A. Mateescu, A. Saloma, “Many-valued truth functions, Černý's conjecture and roadcoloring”, Bull. EATCS, 68 (1999), 134–150 | MR | Zbl

[5] J.-E. Pin, “On two combinatorial problems arising from automata theory”, Ann. Discr. Math., 17 (1983), 535–548 | MR | Zbl

[6] S. Sandberg, “Homing and synchronizing sequences, Model-Based Testing of Reactive Systems”, Lect. Notes Comput. Sci., 3472, 2005, 5–33 | DOI

[7] E. Skvortsov, E. Tipikin, “Experimental study of the shortest reset word of random automata”, Implement. Appl. Automata, Lect. Notes Comput. Sci., 6807, 2011, 290–298 | DOI | MR | Zbl

[8] E. Skvortsov, Yu. Zaks, “Synchronizing random automata”, Discr. Math. Theor. Comput. Sci., 12:4 (2010), 95–108 | MR | Zbl

[9] M. V. Volkov, “Synchronizing automata and the Černý conjecture”, Languages Automata: Theory and Appl., Lect. Notes Comput. Sci., 5196, 2008, 11–27 | DOI | MR | Zbl