# Aperiodic finite state automaton

An **aperiodic finite-state 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]}

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 *xy*^{m}*z* in *L* if and only if *xy*^{n}*z* 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]}

## References

- ↑ 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. - ↑ 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.

- 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. - 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". In Dediu, Adrian-Horia; Inenaga, Shunsuke; Martín-Vide, Carlos.
*Proc. Language and Automata Theory and Applications (LATA)*(PDF). LNCS.**6638**. Springer. pp. 1–21. ISBN 978-3-642-21253-6. — Uses Green's relations to prove Schützenberger's and other theorems.

This article is issued from Wikipedia - version of the 6/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.