Geodesic
Primitive digraphs with large exponents and slowly synchronizing automata
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 9-39 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We exhibit several infinite series of synchronizing automata. The minimum length of reset words for each of the automata is close to the state number squared. All these automata are tightly related to primitive directed graphs with large exponents. 
@article{ZNSL_2012_402_a1,
     author = {D. S. Ananichev and M. V. Volkov and V. V. Gusev},
     title = {Primitive digraphs with large exponents and slowly synchronizing automata},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {9--39},
     year = {2012},
     volume = {402},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a1/}
}
TY  - JOUR
AU  - D. S. Ananichev
AU  - M. V. Volkov
AU  - V. V. Gusev
TI  - Primitive digraphs with large exponents and slowly synchronizing automata
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 9
EP  - 39
VL  - 402
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a1/
LA  - ru
ID  - ZNSL_2012_402_a1
ER  - 
%0 Journal Article
%A D. S. Ananichev
%A M. V. Volkov
%A V. V. Gusev
%T Primitive digraphs with large exponents and slowly synchronizing automata
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 9-39
%V 402
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a1/
%G ru
%F ZNSL_2012_402_a1
D. S. Ananichev; M. V. Volkov; V. V. Gusev. Primitive digraphs with large exponents and slowly synchronizing automata. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 9-39. http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a1/

[1] V. Liskovets, “Chislo svyaznykh initsialnykh avtomatov”, Kibernetika, 1969, no. 3, 16–19 | Zbl

[2] V. N. Sachkov, V. E. Tarakanov, Kombinatorika neotritsatelnykh matrits, TVP, M., 2000 | MR | Zbl

[3] R. L. Adler, L. W. Goodwyn, B. Weiss, “Equivalence of topological Markov shifts”, Israel J. Math., 27 (1977), 49–63 | DOI | MR | Zbl

[4] M. Almeida, N. Moreira, R. Reis, “Enumeration and generation with a string automata representation”, Theor. Comput. Sci., 387 (2007), 93–102 | DOI | MR | Zbl

[5] D. S. Ananichev, V. V. Gusev, M. V. Volkov, “Slowly synchronizing automata and digraphs”, Mathematical Foundations of Computer Science, Lect. Notes Comput. Sci., 6281, 2010, 55–64 | DOI | MR

[6] 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

[7] M. Berlinkov, “Approximating the minimum length of synchronizing words is hard”, Computer Science in Russia, Lect. Notes Comput. Sci., 6072, 2010, 37–47 | DOI | MR | Zbl

[8] M. Berlinkov, “On a conjecture by Carpi and D'Alessandro”, Int. J. Found. Comp. Sci., 22 (2011), 1565–1576 | DOI | MR | Zbl

[9] R. Brualdi, H. Ryser, Combinatorial Matrix Theory, Cambridge University Press, 1991 | MR | Zbl

[10] A. Carpi, F. D'Alessandro, “On the hybrid Černý-Road Coloring Problem and Hamiltonian paths”, Developments in Language Theory, Lect. Notes Comput. Sci., 6224, 2010, 124–135 | DOI | MR | Zbl

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

[12] A. L. Dulmage, N. S. Mendelsohn, “The exponent of a primitive matrix”, Can. Math. Bull., 5 (1962), 241–244 | DOI | MR | Zbl

[13] A. L. Dulmage, N. S. Mendelsohn, “Gaps in the exponent set of primitive matrices”, Ill. J. Math., 8 (1964), 642–656 | MR | Zbl

[14] V. Gusev, “Lower bounds for the length of reset words in Eulerian automata”, Reachability Problems, Lect. Notes Comput. Sci., 6945, 2011, 180–190 | DOI | Zbl

[15] J. Kari, “A counter example to a conjecture concerning synchronizing words in finite automata”, Bull. European Assoc. Theor. Comput. Sci., 73 (2001), 146 | MR | Zbl

[16] J. Olschewski, M. Ummels, “The complexity of finding reset words in finite automata”, Mathematical Foundations of Computer Science, Lect. Notes Comput. Sci., 6281, 2010, 568–579 | DOI | MR | Zbl

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

[18] J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem, Oxford University Press, 2005 | MR | Zbl

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

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

[21] B. Steinberg, “The Černý conjecture for one-cluster automata with prime length cycle”, Theor. Comput. Sci., 412 (2011), 5487–5491 | DOI | MR | Zbl

[22] A. N. Trahtman, “An efficient algorithm finds noticeable trends and examples concerning the Černý conjecture”, Mathematical Foundations of Computer Science, Lect. Notes Comput. Sci., 4162, 2006, 789–800 | DOI | MR | Zbl

[23] A. N. Trahtman, “Notable trends concerning the synchronization of graphs and automata”, Electr. Notes Discr. Math., 25 (2006), 173–175 | DOI | MR | Zbl

[24] A. N. Trahtman, “The road coloring problem”, Israel J. Math., 172 (2009), 51–60 | DOI | MR | Zbl

[25] A. N. Trahtman, “Modifying the upper bound on the length of minimal synchronizing word”, Fundamentals of Computation Theory, Lect. Notes Comput. Sci., 6914, 2011, 173–180 | DOI | MR | Zbl

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

[27] M. V. Volkov, “Synchronizing automata preserving a chain of partial orders”, Theor. Comput. Sci., 410 (2009), 3513–3519 | DOI | MR | Zbl

[28] H. Wielandt, “Unzerlegbare, nicht negative Matrizen”, Math. Z., 52 (1950), 642–648 | DOI | MR | Zbl