Aperiodic finite state automaton explained

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 that 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 xy^mz in L if and only if xyⁿz in L. For these languages, when a string contains enough repetitions of any substring (at least n repetitions), changing the number of repetitions to another number that is at least n cannot change membership in the language. (This is automatically true when y is the empty string, but becomes a nontrivial condition when y is non-empty.) Another way to state Schützenberger's theorem is that star-free languages and counter-free languages are the same thing.

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

References

• Book: McNaughton . Robert . Papert . Seymour . Seymour Papert . With an appendix by William Henneman . Research Monograph . 65 . 1971 . Counter-free Automata . MIT Press . 0-262-13076-9 . 0232.94024 . registration .
• Masters Thesis. Sonal Pratik Patel. An Examination of Counter-Free Automata. 2010. San Diego State University. - An intensive examination of McNaughton, Papert (1971).
• Book: Thomas Colcombet. Green's Relations and their Use in Automata Theory. Proc. Language and Automata Theory and Applications (LATA). 2011. 6638. 1–21. Springer. Dediu, Adrian-Horia . Inenaga, Shunsuke . Martín-Vide, Carlos . LNCS. 978-3-642-21253-6. - Uses Green's relations to prove Schützenberger's and other theorems.

Notes and References

1. Schützenberger, Marcel-Paul. On Finite Monoids Having Only Trivial Subgroups. Information and Control. 1965. 8. 2. 190–194. 10.1016/s0019-9958(65)90108-7. free.
2. 1152.68461 . Trahtman . Avraham N. . Avraham Trahtman . The Černý conjecture for aperiodic automata . . 9 . 2 . 3–10 . 2007 . 1365-8050 . 2014-04-05 . https://web.archive.org/web/20150923215445/http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/downloadSuppFile/649/30 . 2015-09-23 . dead .