Geodesic
Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata
Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 4, pp. 44-56.

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

The notion of carefully synchronizing words for partial finite automata (PFA) is introduced. The careful synchronization of PFA is a natural generalization of the synchronization of the deterministic finite automata. Some lower bounds for the length of the shortest carefully synchronizing words are found for an automaton with a given number of states. It is proven that the maximal length of the shortest reset words for two- and three-letter automata grows faster than any polynomial in the number of states. Tabl. 1, illustr. 3, bibl. 11.
Mots-clés : automata
Keywords: synchronization. 
@article{DA_2008_15_4_a3,
     author = {P. V. Martyugin},
     title = {Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {44--56},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2008_15_4_a3/}
}
TY  - JOUR
AU  - P. V. Martyugin
TI  - Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2008
SP  - 44
EP  - 56
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2008_15_4_a3/
LA  - ru
ID  - DA_2008_15_4_a3
ER  - 
%0 Journal Article
%A P. V. Martyugin
%T Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata
%J Diskretnyj analiz i issledovanie operacij
%D 2008
%P 44-56
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2008_15_4_a3/
%G ru
%F DA_2008_15_4_a3
P. V. Martyugin. Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata. Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 4, pp. 44-56. http://geodesic.mathdoc.fr/item/DA_2008_15_4_a3/

[1] Bach E., Shallit J., Algorithmic number theory. Vol. I: Efficient Algorithms, MIT Press, Cambridge, MA, 1996, 506 pp. | MR | Zbl

[2] Černý J., “Poznámka k homogénnym eksperimentom s konecnými avtomatami”, Mat.-Fyz. Cas. Slovensk. Akad. Vied., 14 (1964), 208–216 | MR | Zbl

[3] Dubuc L., “Sur les automates circulaires et la conjecture de Černý”, RAIRO Inform. Theor. Appl., 32 (1998), 21–34 | MR

[4] Eppstein D., “Reset sequences for monotonic automata”, SIAM J. Comput., 19 (1990), 500–510 | DOI | MR | Zbl

[5] Finch S. R., Mathematical constants, Cambridge University Press, Cambridge, 2003, 602 pp. | MR

[6] Ito M., Algebraic theory of automata and languages, World Scientific, Singapore, 2004, 199 pp. | MR

[7] Ito M., Shikishima-Tsuji K., “Some results on directable automata”, Theory is forever, Essays dedicated to Arto Salomaa on the occasion of his 70th birthday, Lect. Notes Comp. Sci., 3113, Springer-Verl., Berlin–Heidelberg–New York, 2004, 125–133 | MR | Zbl

[8] Kari J., “Synchronizing finite automata on Eulerian digraphs”, Math. foundations comput. Sci. 26th Internat. symp. (Marianske Lazne, 2001), Lect. Notes Comput. Sci., 2136, Springer, Berlin, 432–438 | MR | Zbl

[9] Martyugin P. V., “Lower bounds for length of shortest carefully synchronizing words”, CSR 2006, Workshop on Words and Automata, CD Proceedings, St. Petersburg, 2006

[10] Natarajan B. K., “Some paradigms for the automated design of parts feeders”, Internat. J. Robotics Research, 8:6 (1989), 89–109

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