Aperiodic finite state automaton
An aperiodic finite-state automaton (also called a counter-free automaton) is a finite-state automaton whose transition monoid is aperiodic.
Properties
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] In particular, the minimum automaton of a star-free language is always counter-free (however, a star-free language may also be recognized by other automata which are not aperiodic).
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 m ≥ n we have xymz in L if and only if xynz in L. Another way to state Schützenberger's theorem is that star-free languages and counter-free languages are the same thing.[further explanation needed]
An aperiodic automaton satisfies the Černý conjecture.[2]
References
- ↑ Schützenberger, Marcel-Paul (1965). "On Finite Monoids Having Only Trivial Subgroups". Information and Control 8 (2): 190–194. doi:10.1016/s0019-9958(65)90108-7. http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1965-4TrivialSubgroupsIC.pdf.
- ↑ Trahtman, Avraham N. (2007). "The Černý conjecture for aperiodic automata". Discrete Math. Theor. Comput. Sci. 9 (2): 3–10. ISSN 1365-8050. http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/downloadSuppFile/649/30. Retrieved 2014-04-05.
- McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph. 65. With an appendix by William Henneman. MIT Press. ISBN 0-262-13076-9. https://archive.org/details/CounterFre_00_McNa.
- Sonal Pratik Patel (2010). An Examination of Counter-Free Automata (PDF) (Masters Thesis). San Diego State University. — An intensive examination of McNaughton, Papert (1971).
- Thomas Colcombet (2011). "Green's Relations and their Use in Automata Theory". Proc. Language and Automata Theory and Applications (LATA). LNCS. 6638. Springer. pp. 1–21. ISBN 978-3-642-21253-6. http://www.liafa.jussieu.fr/~colcombe/Publications/LATA11-colcombet.pdf. — Uses Green's relations to prove Schützenberger's and other theorems.
 |  |
