Sur les automates circulaires et la conjecture de Černý
Dubuc, L.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 32 (1998), p. 21-34 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1998-01-01
@article{ITA_1998__32_1-3_21_0,
     author = {Dubuc, L.},
     title = {Sur les automates circulaires et la conjecture de \v Cern\'y},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {32},
     year = {1998},
     pages = {21-34},
     mrnumber = {1657507},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/ITA_1998__32_1-3_21_0}
}

Dubuc, L. Sur les automates circulaires et la conjecture de Černý. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 32 (1998) pp. 21-34. http://gdmltest.u-ga.fr/item/ITA_1998__32_1-3_21_0/

[Čer64] J. Černý, Poznámka k homogénnym experimenton s konečnými automatmi, Mat. fyz. čas. SAV., 1964, 14, p. 208-215. | MR 168429 | Zbl 0137.01101

[Čer71] J. Černý, On directable automata, Kybernetika, 1971, 7, p. 4. | MR 302347 | Zbl 0223.94029

[Dub96] L. Dubuc, Les automates circulaires biaises vérifient la conjecture de Černý, Informatique théorique et Applications, 1996, 30, n° 6, p. 495-505. | Numdam | MR 1454826 | Zbl 0877.68083

[Epp90] D. Eppstein, Reset sequences for monotonic automata, SIAM J. Comput, June 1990, 19, 3, p. 500-510. | MR 1041543 | Zbl 0698.68058

[Fra82] P. Frankl, An extremal problem for two families of sets, Europ. J. Combinatorics, 1982, p. 125-127. | MR 670845 | Zbl 0488.05004

[Gor92] P. Goralčík et V. Koubek, Rank problems for composite transformations, IJAC, 1995, 5, n° 3, p. 309-316. | MR 1331737 | Zbl 0831.20089

[Koh70] Z. Kohavi, Switching and Finite Automata Theory, McGraw-Hill, New York, 1970, p. 414-416. | MR 411805 | Zbl 0206.47701

[Pin77] 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. | MR 439469 | Zbl 0364.94073

[Pin78a] J.-E. Pin, Sur un cas particulier de la conjecture de Černý, Communication 5e colloque "On automata languages and programming" 1978, Udine (Italie). | MR 520853 | Zbl 0389.68036

[Pin78b] 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.

[Pin78c] J.-E. Pin, Sur un cas particulier de la conjecture de Černý, Proc. 5th ICALP, Lect. Notes in Comp. Sci., Springer Verlag, Berlin, Heidelberg, New York, 1978, 62, p. 345-352. | MR 520853 | Zbl 0389.68036

[Pin78d] J.-E. Pin, Sur les mots synchronisants dans un automate fini, Elektron. Informationsverarb. Kybernet., 1978, 14, p. 293-303. | MR 530266 | Zbl 0392.68051

[Pin78e] 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. | Zbl 0482.68053

[Pin81] J.-E. Pin, Le problème de la synchronisation et la conjecture de Černý, Noncommutative structures in algebra and geometrie combinatorics, De Luca, A.ed., Quaderni de la Ricerca Scientifica, CNR, Roma, 1981, 109, p. 37-48. | MR 646476 | Zbl 0543.68039

[Pin83] J.-E. Pin, On two combinatorial problems arising from automata theory, Annals of Discrete Mathematics, 1983, 17, p. 535-548. | MR 841339 | Zbl 0523.68042

[Rys95] I. K. Rystsov, Quasioptimal bounds for the length of reset words for regular automata, Acta Cybernetica, 1995, 12, n° 2, p. 145-152. | MR 1370976 | Zbl 0844.68085

[Sav] P. Savický et S. Vanĕček, Search of synchronizing words for finite automata with aid of linear algebra, unpublished manuscript.

[Sta66] P. H. Starke, Eine Bemerkung über homogene Experimente, Elektron. Information-verarbeit. Kybernetik, 1966, 2, p. 257-259. | Zbl 0166.27003

[Sta69] P. H. Starke, Abstrakte Automaten, VEB Deutscher Verlag der Wissenschaft, (1969), Abstract Automata, North Holland, Amsterdam, (1972). | MR 276016 | Zbl 0182.02102