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 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]
References
- Lua error in package.lua at line 80: module 'strict' not found.
- Lua error in package.lua at line 80: module 'strict' not found. — An intensive examination of McNaughton, Papert (1971).
- Lua error in package.lua at line 80: module 'strict' not found. — Uses Green's relations to prove Schützenberger's and other theorems.
<templatestyles src="Asbox/styles.css"></templatestyles>
