Abstract
A word w is called synchronizing (recurrent, reset, magic, directable) word of deterministic finite automaton (DFA) if w sends all states of the automaton to a unique state. In 1964 Jan Černy found a sequence of n-state complete DFA possessing a minimal synchronizing word of length (n − 1)2. He conjectured that it is an upper bound on the length of such words for complete DFA. Nevertheless, the best upper bound (n 3 − n)/6 was found almost 30 years ago.
We reduce the upper bound on the length of the minimal synchronizing word to n(7n 2 + 6n − 16)/48.
An implemented algorithm for finding synchronizing word with restricted upper bound is described. The work presents the distribution of all synchronizing automata of small size according to the length of an almost minimal synchronizing word.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ananichev, D., Gusev, V., Volkov, M.: Slowly Synchronizing Automata and Digraphs. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 55–65. Springer, Heidelberg (2010)
Béal, M.P., Czeizler, E., Kari, J., Perrin, D.: Unambiguous automata. Math. Comput. Sci. 1, 625–638 (2008)
Černy, J.: Poznamka k homogenym eksperimentom s konechnymi automatami. Math.-Fyz. Čas 14, 208–215 (1964)
Černy, J., Piricka, A., Rosenauerova, B.: On directable automata. Kybernetika 7, 289–298 (1971)
Frankl, P.: An extremal problem for two families of sets. Eur. J. Comb. 3, 125–127 (1982)
Friedman, J.: On the road coloring problem. Proc. of the Amer. Math. Soc. 110, 1133–1135 (1990)
Kari, J.: A counter example to a conjecture concerning synchronizing word in finite automata. EATCS Bulletin 73, 146–147 (2001)
Kari, J.: Synchronizing Finite Automata on Eulerian Digraphs. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 432–438. Springer, Heidelberg (2001)
Kljachko, A.A., Rystsov, I.K., Spivak, M.A.: An extremely combinatorial problem connected with the bound on the length of a recurrent word in an automata. Kybernetika, 216–225 (1987)
Pin, J.-E.: On two combinatorial problems arising from automata theory. Annals of Discrete Math 17, 535–548 (1983)
Roman, A.: Experiments on Synchronizing Automata. Schedae Informaticae 19, 35–51 (2010)
Steinberg, B.: The Averaging Trick and the Čern’́y Conjecture. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol. 6224, pp. 423–431. Springer, Heidelberg (2010)
Trahtman, A.N.: The Cerny Conjecture for Aperiodic Automata. Discr. Math. and Theoret. Comput. Sci. 9(2), 3–10 (2007)
Trahtman, A.N.: The Road Coloring and Černy Conjecture. In: Proc. of Prague Stringology Conference, pp. 1–12 (2008)
Trahtman, A.N.: Notable trends concerning the synchronization of graphs and automata. CTW06, El. Notes in Discrete Math. 25, 173–175 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Trahtman, A.N. (2011). Modifying the Upper Bound on the Length of Minimal Synchronizing Word. In: Owe, O., Steffen, M., Telle, J.A. (eds) Fundamentals of Computation Theory. FCT 2011. Lecture Notes in Computer Science, vol 6914. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22953-4_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-22953-4_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22952-7
Online ISBN: 978-3-642-22953-4
eBook Packages: Computer ScienceComputer Science (R0)