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 celebrated result of algebraic automata theory is due to Marcel-Paul Schützenberger.[1]

An aperiodic automaton satisfies the Cerny conjecture.[2]

References

  1. ^ Schützenberger, Marcel-Paul, "On finite monoids having only trivial subgroups," Information and Control, Vol 8 No. 2, pp. 190-194, 1965.
  2. ^ Trahtman. "The Cerny conjecture for aperiodic automata," Discrete Mathematics and Theoretical Computer Science, Vol 9 No. 2, pp. 133-138, 2007.