On the directability of automata. (English) Zbl 0718.68053

Summary: We present some partial results on the hypothesis due to J. Černý [Poznámka k homogénnym experimentom s konečnými automatmi. Mat. fyz. čas. SAV 14, 208-215 (1964)] and a necessary and sufficient condition for the directability of an automaton.


68Q45 Formal languages and automata
Full Text: EuDML Link


[1] J. Černý: Poznámka k homogennym experimentom s konečnými automatmi. Mat. fyz. čas. SAV 14 (1964), 208-215.
[2] J. Černý A. Pirická, B. Rosenauerová: On directable automata. Kybernetika 7 (1971), 289-297. · Zbl 0223.94029
[3] J. E. Pin: Le problème de la synchronisation, Contribution à l’étude de la conjecture de Černý. Thèse, 3e cycle, Paris 1978.
[4] J. E. Pin: Le problème de la synchronisation et la conjecture de Černý. Non Commutative Structures in Algebra and Geometric Combinatorics (A. De Luca, CNR (1978), pp. 46-58.
[5] J. E. Pin: On two combinatorial problems arising from automata theory. Ann. Discrete Math. 17(1983), 535-548. · Zbl 0523.68042
[6] J. E. Pin: Sur les mots synchronisants dans un automate fini. Elektron. Informationsverarb. Kybernet. 14 (1978), 283-289. · Zbl 0392.68051
[7] J. E. Pin: Sur un cas particulier de la conjecture de Černý. Automata, Languages and Programming – Proceedings 5th International Conference (G. Ausiello, C. Böhm, (Lecture Notes in Computer Science 62), Springer-Verlag, Berlin–Heidelberg–New York 1978, pp. 345-352. · Zbl 0389.68036
[8] P. H. Starke: Eine Bemerkung über homogene Experimente. Elektron. Informationsverarb. Kybernet. 2 (1966), 257-259. · Zbl 0166.27003
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.