Cerný's conjecture

This page is deprecated. The reading of the beautiful thorough survey of M. Volkov Synchronizing automata and the Cerný's conjecture is highly recommended. It contains updated references and presents several results and open problems related to the Cerný's conjecture.

### Cerný's conjecture.

Let A = (Q, A, .) be a deterministic automaton with n states (the initial state and the final states do not play any role in this conjecture). A word w is said to be synchronizing in A if there exists a state p in Q such that, for every q in Q, q.w = p. For instance, in the automaton represented below, the word ba3ba3b is synchronizing, since 0.ba3ba3b = 1.ba3ba3b = 2.ba3ba3b = 3.ba3ba3b = 0. An automaton is synchronizing if it admits a synchronizing word. Figure 1. A synchronizing automaton with 4 states.

Cerný's conjecture states that if an n-state automaton is synchronizing, then it admits a synchronizing word of length ≤ (n-1)2. In our example, the word ba3ba3b has length 9 = (4-1)2.

### Words of rank (n-k).

In 1978, I proposed the following generalisation of Cerný's conjecture. Let A be an n-state automaton. Each word w defines a map from Q to Q. The rank of w in A is the size of its image (or codomain). Its deficiency in A is the integer n-k. The deficiency of A is the minimum of the deficiency of a word in A. For instance, if Ais the automaton represented in Figure 1, the word w = ba3b has rank 2, since 0.w = 0, 1.w = 0, 2.w = 1 and 3.w = 0. The deficiency of w is 2 = 4 - 2. The deficiency of A is 1. The computation of all the images of our example is done in Figure 2. Figure 2. Computation of the images.
In our example, n = 4 and, for k = 0, the empty word (of length 0) has rank 4 = n - 0, the word b (of length 1) has rank 3 = (n-1), the word ba2b (of length 4 = (n-2)2) has rank 2 = (n-2) and the word ba3ba3b (of length 9 = (4-1)2) has rank 1 = (n-3). The conjecture can be stated as follows:
Deficiency conjecture. If an automaton admits a word of deficiency ≥ k, then there exists such a word of length ≤ k2.
Intuitively, it means for instance that a word of length ≤ 9 should suffice to reach rank 7 in a 10-state automaton and that the same length 9 should suffice to reach rank 9997 in a 10000-state automaton. Cerný's conjecture corresponds to the case k = n-1.
The conjecture was proved to be true for k = 0, 1, 2, 3 but a counterexample, shown in Figure 3, was found by Jarkko Kari for k = 4. Figure 3. A counterexample.
In this automaton, the shortest words of rank 2 are baabababaabbabaab and baababaabaababaab. Both have length 17, contradicting the upper bound (6-2)2 = 16.

In view of this counterexample, Volkov suggested to restrict the deficiency conjecture to automata of deficiency k.
Volkov's deficiency conjecture. In an automaton of deficiency k there exists such a word of deficiency k and of length ≤ k2.
No counterexample to this improved version of the deficiency conjecture has been found so far.

### History and known results.

Cerný's conjecture was first stated in 1964. Various bounds have been obtained
2n - n - 1       (1964, Cerný )
1
2
n3 -
3
2
n2 + n + 1
(1966, Starke, 1969, Starke)
1
2
n3 - n2 +
n
2

(1970, Kohavi)
1
3
n3 - n2
1
3
n + 6
(1970, Paterson, personal communication to D.J. Kfoury)
1
3
n3
3
2
n2
25
6
n - 4
(1971, Cerný, Pirick� et Rosenauerova)
7
27
n3
17
18
n2
17
6
n - 3
for n multiple of 3 (1977, Pin)
1
6
n3
-
1
6
n - 1
(1983, Pin)

The best estimate on the deficiency conjecture known so far is due to Pin, 1983.

### Extensions.

Several extensions to the Cerný's conjecture have been proposed. We discuss two of them.

#### Universally deficient words.

A word of deficiency ≥ k (in an automaton A) is also called k-deficient. An automaton is k-deficient if admits a k-deficient word. A word w in A* is universally k-deficient if its k-deficient in each k-deficient automaton A on the alphabet A.

Sauer and Stone proved in 1991 that universally n-deficient words exist for every n and every alphabet A. An open problem is to find, for each n and k, the length of a shortest universally n-deficient word on a k-letter alphabet.

For instance, it is shown in [Sauer and Stone, Corollary 3.4] that the word aba2b2ab is universally 2-deficient, and it can be checked that except this word and its mirror image, no word of length 8 over {a, b} is universally 2-deficient.

### References.

1. D. S. Ananichev, M.V. Volkov, Collapsing words vs. synchronizing words, LNCS 2295 (2002), 166-174.
2. Dimitry S. Ananichev, and Mikhail V. Volkov, Synchronizing monotonic automata, DLT 2003, Z. Ésik and Z. Fülöp eds., LNCS 2710 (2003), 111-121.
3. D. S. Ananichev, A. Cherubini, M.V. Volkov, An Inverse Automata Algorithm for Recognizing 2-collapsing words, 6-th ICDLT, Kyoto, Japan, 2002, LNCS 2450 (2003), 270-382.
4. M. P. Béal, A note on Cerný's Conjecture and rational series, preprint IGM 2003-05.
5. J. Cerný , Poznámka k. homogénnym experimentom s konecnymi automatmi, Mat. fyz. cas SAV 14 (1964), 208--215.
6. J. Cerný, A. Pirická and B. Rosenauerova, On directable automata, Kybernetica 7 (1971), 289--298.
7. L. Dubuc, Les automates circulaires biaisés vérifient la conjecture de Cerný, Inform. Theor. Appl. 30 (1996), 495--505.
8. L. Dubuc, Les automates circulaires et la conjecture de Cerný, Inform. Theor. Appl. 32 (1998), 21--34.
9. D. Eppstein, Reset sequences for monotonic automata, SIAM J. Comput. 19 (1990), 500--510.
10. P. Frankl, An extremal problem for two families of sets, Eur. J. Comb. 3 (1982), 125--127.
11. S. Ginsburg, On the length of the smallest uniform experiment which distinguishes the terminal states of a machine, J. Assoc. Comput. Mach. 5 (1958), 266--280.
12. W. Göhring, Minimal Initializing Word: A Contribution to Cerný's Conjecture, Journal of Automata, Languages and Combinatorics 4 (1997), 209--226.
13. B. Imreh, M. Steinby, Some remarks on directable automata, Acta Cybernet. 1, 12 (1995) 23-35.
14. Jarkkho Kari, A counter example to a conjecture concerning synchronizing words in finite automata, EATCS Bulletin 73 (2001), 146.
15. D.J. Kfoury, Synchronizing sequences for probabilistic automata, Studies in Applied Math. XLIX, 1 (1970) 101-103.
16. A.A. Klyachko, I.K. Rystsov and M.A. Spivak, An extremal combinatorial problem associated with the bound of the length of a synchronizing word in an automaton, Kibernetika 2 (1987), 16--20. (in Russian); Engl. translation: Cybernetics 23 (1987) 165--171.
17. Z. Kohavi, Switching and finite automata theory, McGraw-Hill Book Co., NY, 1970.
18. Z. Kohavi and J. Winograd, Bounds on the length of synchronizing sequences and the order of information losslessness, in Proc. of an international Symposium on the Theory of Machines and Computations, Haifa, Israel, 1970.

19. Z. Kohavi, J. Winograd, Establishing certain bounds concerning finite automata, J. Comp. System Sci. 7 (1973) 288-299.
20. S.W. Margolis, J.-E. Pin and M.V.Volkov, Words guaranteeing minimal image, Words, Languages & Combinatorics III, Masami Ito and Teruo Imaoka eds., World Scientific, 2003, 297-310. Abstract, PostScript gzipped file, PDF file
21. A. Mateescu and A. Salomaa, Many-valued truth functions, Cerný's conjecture and road coloring, EATCS Bulletin 68, 1999, 134--150.
22. J.-E. Pin, Sur la longueur des mots de rang donné d'un automate fini, CRAS 284 (1977), 1233--1235. Abstract, PostScript gzipped file, PDF file
23. J.-E. Pin, Le problème de la synchronisation et la conjecture de Cerný, Thèse de 3ème cycle, Université Paris VI, 1978.
24. J.-E. Pin, Sur les mots synchronisants dans un automate fini, Elektron. Informationsverarb. Kybernet. 14 (1978), 293--303.
25. J.-E. Pin, Sur un cas particulier de la conjecture de Cerný, in 5th ICALP, Berlin, 1978, pp. 345-352, LNCS 62, Springer. Abstract, PostScript gzipped file, PDF file
26. J.-E. Pin, Utilisation de l'algèbre linéaire en théorie des automates, in Actes du 1er Colloque AFCET-SMF de Mathématiques Appliquées, pp. 85--92, AFCET, 1978. Abstract, PostScript gzipped file, PDF file
27. J.-E. Pin, Le problème de la synchronisation et la conjecture de Cerný, in Non-commutative structures in algebra and geometric combinatorics, A. De luca (éd.), pp. 37--48, Quaderni de la Ricerca Scientifica 109, CNR, Roma, 1981. Abstract, PostScript gzipped file, PDF file
28. J.-E. Pin, On two combinatorial problems arising from automata theory, Annals of Discrete Mathematics 17 (1983), 535--548.
29. R. Pöschel, M. V. Sapir, N. Sauer, M. Stone and M. V. Volkov, Identities in full transformation semigroups, Algebra Universalis 31 (1994), 580--588.
30. I.K. Rystsov, A quadratic bound on the length of the recurrent word in a regular automaton. Dok. Acad. Nauk Ukr., 9 (1992) 5-8.
31. I.K. Rystsov, The rank of the finite automaton. Cybernetics and System An. 3 (1992) 3-10.
32. I.K. Rystsov, Almost optimal bound of recurrent word length for regular automata, Kibern. Sist. Anal. 5 (1995), 40--48. (in Russian); Engl. translation: Cybern. Syst. Anal. 31 (1995) 669--674.
33. I.K. Rystsov, Quasioptimal bound for the length of reset words for regular automata, Acta Cybern. 12 (1995), 145--152.
34. I.K. Rystsov, Reset words for commutative and solvable automata. Theoret. Comput. Sci. 172 (1997) 273-279.
35. A. Salomaa, Generation of constants and synchronization of finite automata, J. of Univers. Comput. Sci. 8(2002), 332-347.
36. N. Sauer and M. Stone, Composing functions to reduce image size, Arc Combinatoria 31 (1991), 171--176.
37. P. H. Starke, Eine Bemerkung über homogene Experimente., Elektr. Informationverarbeitung und Kyb. 2 (1966), 257--259.
38. A. N. Trahtman, The existence of synchronising word and Cerný conjecture for some finite automata, to appear in Discrete Appl. Math, 2002

The automata of this page were produced with the LaTeX package gastex