Abstract
We introduce the notion of careful synchronization for partial finite automata as a natural generalization of the synchronization notion for complete finite automata. We obtain a lower bound for the careful synchronization threshold for automata with a given number of states.
Similar content being viewed by others
References
J. Černý, “Poznámka kHomogénnym Eksperimentom s Konečnými Automatami,” Mat.-Fyz. Cas. Slovensk. Akad. Vied. 14(3), 208–216 (1964).
L. Dubuc, “Sur les Automates Circulaires et la Conjecture de Černý,” RAIRO Inform. Theor. Appl. 32(1–3), 21–34 (1998).
D. Eppstein, “Reset Sequences for Monotonic Automata,” SIAM J. Comput. 19(3), 500–510 (1990).
J. Kari, “Synchronizing Finite Automata on Eulerian Digraphs,” Theoret. Comput. Sci. 295(1–3), 223–232 (2003).
J.-E. Pin, “On Two Combinatorial Problems Arising From Automata Theory,” Ann. Discrete Math. 17, 535–548 (1983).
M. Ito and K. Shikishima-Tsuji, “Some Results on Directable Automata,” in: Theory Is Forever. Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday (Lect. Notes Comp. Sci., Springer, Berlin, 2004), Vol. 3113, pp. 125–133.
M. Ito, Algebraic Theory of Automata and Languages (World Scientific, Singapore, 2004).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © P.V. Martyugin, 2010, published in Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2010, No. 1, pp. 59–68.
About this article
Cite this article
Martyugin, P.V. A lower bound for the length of the shortest carefully synchronizing words. Russ Math. 54, 46–54 (2010). https://doi.org/10.3103/S1066369X10010056
Received:
Published:
Issue Date:
DOI: https://doi.org/10.3103/S1066369X10010056