Aperiodic finite state automaton
From Wikipedia, the free encyclopedia
An aperiodic finite-state automaton is a finite-state automaton whose transition monoid is aperiodic.
[edit] 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 celebrated 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]
[edit] References
- ^ Schützenberger, Marcel-Paul, "On finite monoids having only trivial subgroups," Information and Control, Vol 8 No. 2, pp. 190-194, 1965.
- ^ 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.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| P ≟ NP | This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. |
