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.

Definition

A finite-state automaton is counter-free if the following property is true:

as long as there is a loop in the automaton that can be taken with a word $u^{m}$ (i.e. word $u$ repeated $m$ times) for $m\geq 1$ from state $q$ to state $q$ , then we also go from $q$ to $q$ by reading word $u$ .^[1]^{[page needed]}

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.^[2] 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.^[3]

References

↑ Diekert, Volker; Gastin, Paul. "First-order definable languages" (PDF).
↑ 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. Archived from the original on 2015-09-23. Retrieved 2014-04-05.

McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph. Vol. 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 (eds.). Proc. Language and Automata Theory and Applications (LATA) (PDF). LNCS. Vol. 6638. Springer. pp. 1–21. ISBN 978-3-642-21253-6. — Uses Green's relations to prove Schützenberger's and other theorems.

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by adding missing information.

[1] Diekert, Volker; Gastin, Paul. "First-order definable languages" (PDF).

[Schutzenberger65-2] 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.

[Trahtman07-3] 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. Archived from the original on 2015-09-23. Retrieved 2014-04-05.

[1]

[2]

[3]