Aperiodic finite state automaton

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

An aperiodic finite-state automaton is a finite-state automaton whose transition monoid is aperiodic.


A regular language is star-free if and only if it is accepted by an automaton with a finite and aperiodic transition monoid. This result of algebraic automata theory is due to Marcel-Paul Schützenberger.[1]

A counter-free language is a regular language for which there is an integer n such that for all words x, y, z and integers mn we have xymz in L if and only if xynz in L. A counter-free automaton is a finite-state automaton which accepts a counter-free language. A finite-state automaton is counter-free if and only if it is aperiodic.

An aperiodic automaton satisfies the Černý conjecture.[2]


  1. Schützenberger, Marcel-Paul (1965). "On Finite Monoids Having Only Trivial Subgroups" (PDF). Information and Control. 8 (2): 190–194. doi:10.1016/s0019-9958(65)90108-7.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  2. Trahtman, Avraham N. (2007). "The Černý conjecture for aperiodic automata". Discrete Math. Theor. Comput. Sci. 9 (2): 3–10. ISSN 1365-8050. Zbl 1152.68461.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  • McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph. 65. With an appendix by William Henneman. MIT Press. ISBN 0-262-13076-9. Zbl 0232.94024.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  • Sonal Pratik Patel (2010). An Examination of Counter-Free Automata (PDF) (Masters Thesis). San Diego State University.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles> — An intensive examination of McNaughton, Papert (1971).
  • Thomas Colcombet (2011). "Green's Relations and their Use in Automata Theory". In Dediu, Adrian-Horia and Inenaga, Shunsuke and Martín-Vide, Carlos (ed.). Proc. Language and Automata Theory and Applications (LATA) (PDF). LNCS. 6638. Springer. pp. 1–21. ISBN 978-3-642-21253-6.CS1 maint: multiple names: editors list (link)<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles> — Uses Green's relations to prove Schützenberger's and other theorems.