The biased circular automata which verify Černý’s conjecture. (Les automates circulaires biaisés vérifient la conjecture de Černý.) (French) Zbl 0877.68083

Summary: An action \(X\times A^+\to X: (x,w)\mapsto x*w\) of the free semigroup \(A^+\) over the alphabet \(A\) is synchronized by a word \(w\in A^+\) if \(x*w= y*w\) for all \(x,y\in X\). Černý conjectured that if there is such a \(w\) and \(|X|=n\), then there is one of length \(\leq(n-1)^2\). The conjecture remains open, except for particular classes of actions. An action is circular if there is \(c\in A\) acting as a circular permutation, and biased if there is \(b\in A\) with only one \(x\in X\) such that \(|x*b^{-1}|\geq 2\). We confirm the Černý conjecture for biased circular actions.


68Q45 Formal languages and automata
Full Text: DOI EuDML


[1] J. ČERNÝ et K. POZNÁMKA, Homogénnym experimenton s Konečnými automatmi. Mat. fyz. cas. SAV., 1964, 14, p. 208-215. Zbl0137.01101 MR168429 · Zbl 0137.01101
[2] J. ČERNÝ, On directable automata, Kybernetïka 7, 1971, p. 4. Zbl0223.94029 MR302347 · Zbl 0223.94029
[3] P. FRANKL, An extremal problem for two families of sets, Europ, J. Combinatorics, 1982, p. 125-127. Zbl0488.05004 MR670845 · Zbl 0488.05004 · doi:10.1016/S0195-6698(82)80025-5
[4] P. GORALČÍK et V. KOUBEK, Rank problems for composite transformations, à paraître dans IJAC. Zbl0831.20089 · Zbl 0831.20089 · doi:10.1142/S0218196795000185
[5] Z. KOHAVI, Switching and Finite Automata Theory, McGraw-Hill, New York, 1970, p. 414-416. Zbl0206.47701 MR411805 · Zbl 0206.47701
[6] J. E. PIN, Sur la longueur des mots de rang donné d’un automate fini, C. R. Acad. Sc. A, 1977, 284, p. 1233-1235. Zbl0364.94073 MR439469 · Zbl 0364.94073
[7] J. E. PIN, Sur un cas particulier de la conjecture de Černý, Communication faite au 5e colloque ”On automata languages and programming”, 1978, Udine (Italie). Zbl0389.68036 MR520853 · Zbl 0389.68036
[8] J. E. PIN, Le problème de la synchronisation. Contribution à l’étude de la conjecture de Černý, Thèse de 3e cycle à l’université Pierre et Marie Curie (Paris 6), 1978.
[9] J. E. PIN, Sur un cas particulier de la conjoncture de Černý, Proc. 5th ICALP, Lect. Notes in Comp. Sci 62, Springer Verlag, Berlin, Heidelberg, New York, 1978, p. 345-352. Zbl0389.68036 MR520853 · Zbl 0389.68036
[10] J. E. PIN, Sur les mots synchronisants dans un automate fini, Elektron. Informationsverarb. Kybernet., 1978, 14, p. 293-303. Zbl0392.68051 MR530266 · Zbl 0392.68051
[11] J. E. PIN, Utilisation de l’algèbre linéaire en théorie des automates, Actes du 1er Colloque AFCET-SMF de Mathématiques Appliquées, AFCET, 1978, p. 85-92. Zbl0482.68053 · Zbl 0482.68053
[12] J. E. PIN, Le problème de la synchronisation et la conjecture de Černý, Non-commutative structures in algebra and geometric combinatorics, De Luca, A. éd., Quaderni de la Ricerca Scientifica, CNR, Roma, 1981, 109, p. 37-48. Zbl0543.68039 MR646476 · Zbl 0543.68039
[13] J. E. PIN, On two combinatorial problems arising from automata theory, Annals of Discrete Mathematics, 1983, 17, p. 535 -548. Zbl0523.68042 MR841339 · Zbl 0523.68042 · doi:10.1016/S0304-0208(08)73432-7
[14] P. SAVICKÝ et S. VANĔČEK, Search of synchronizing words for finite automata with aid of linear algebra, unpublished manuscript.
[15] (Sta 66] P. H. STARKE, Eine Bemerkung über homogene Experimente, Elektron. Information-verarbeit. Kybernetik, 1966, 2, p. 257-259. Zbl0166.27003 · Zbl 0166.27003
[16] P. H. STARKE, Abstrakte Automaten, VEB Deutscher Verlag der Wissenschaft, 1969, Abstract Automata, North Holland, Amsterdam, 1972. Zbl0182.02102 MR276016 · Zbl 0182.02102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.