Geodesic
Slowly Synchronizing Automata with Zero and Uncovering Sets
Matematičeskie zametki, Tome 90 (2011) no. 3, pp. 422-430.

Voir la notice de l'article provenant de la source Math-Net.Ru

Using the combinatorial properties of uncovering sets in a free monoid, we construct a series of finite deterministic synchronizing automata with zero for which the shortest synchronizing word has length $n^2/4+n/2-1$, where $n$ is the number of states.
Keywords: free monoid, uncovering set, deterministic and nondeterministic automaton, synchronizing automaton (with zero), synchronizing word
Mots-clés : maximal code. 
@article{MZM_2011_90_3_a7,
     author = {E. V. Pribavkina},
     title = {Slowly {Synchronizing} {Automata} with {Zero} and {Uncovering} {Sets}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {422--430},
     publisher = {mathdoc},
     volume = {90},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2011_90_3_a7/}
}
TY  - JOUR
AU  - E. V. Pribavkina
TI  - Slowly Synchronizing Automata with Zero and Uncovering Sets
JO  - Matematičeskie zametki
PY  - 2011
SP  - 422
EP  - 430
VL  - 90
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2011_90_3_a7/
LA  - ru
ID  - MZM_2011_90_3_a7
ER  - 
%0 Journal Article
%A E. V. Pribavkina
%T Slowly Synchronizing Automata with Zero and Uncovering Sets
%J Matematičeskie zametki
%D 2011
%P 422-430
%V 90
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2011_90_3_a7/
%G ru
%F MZM_2011_90_3_a7
E. V. Pribavkina. Slowly Synchronizing Automata with Zero and Uncovering Sets. Matematičeskie zametki, Tome 90 (2011) no. 3, pp. 422-430. http://geodesic.mathdoc.fr/item/MZM_2011_90_3_a7/

[1] A. Mateescu, A. Salomaa, “Many-valued truth functions, Černý's conjecture and road coloring”, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 68 (1999), 134–150 | MR | Zbl

[2] S. Sandberg, “Homing and synchronizing sequences”, Model-Based Testing of Reactive Systems, Lecture Notes in Comput. Sci., 3472, Springer-Verlag, Berlin, 2005, 5–33 | MR | Zbl

[3] M. V. Volkov, “Synchronizing automata and the Černý conjecture”, Languages and Automata: Theory and Applications, Lecture Notes in Comput. Sci., 5196, Springer-Verlag, Berlin, 2008, 11–27 | MR | Zbl

[4] J. Černý, “Poznamka k homogennym eksperimentom s konecnymi automatami”, Mat.-Fyz. Časopis Sloven. Akad. Vied., 14:3 (1964), 208–216 | MR | Zbl

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

[6] I. Rystsov, “Reset words for commutative and solvable automata”, Theoret. Comput. Sci., 172:1-2 (1997), 273–279 | DOI | MR | Zbl

[7] P. V. Martugin, “A series of slowly synchronizing automata with a zero state over a small alphabet”, Inform. and Comput., 206:9-10 (2008), 1197–1203 | DOI | MR | Zbl

[8] D. Ananichev, V. Gusev, M. Volkov, “Slowly synchronizing automata and digraphs”, Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci., 6281, Springer-Verlag, Berlin, 2010, 55–65 | Zbl

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

[10] A. Restivo, “Some remarks on complete subsets of a free monoid”, Noncommutative Structures in Algebra and Geometric Combinatorics, Quad. “Ricerca Sci.”, 109, CNR, Rome, 1981, 19–25 | MR | Zbl

[11] L. Giambruno, A. Restivo, “An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid”, Theor. Inform. Appl., 42:3 (2008), 503–524 | DOI | MR | Zbl

[12] M. Ito, Algebraic Theory of Automata and Languages, World Sci. Publ., Singapore, 2004 | MR | Zbl