An aperiodic finite-state automaton (also called a counter-free automaton) is a

finite-state automaton A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...

whose

transition monoid In mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton having inputs but no output. It consists of a set ''Q'' of states, a set Σ called the input alphabet, and a function ''T'': ''Q'' × Σ → ''Q'' ...

is aperiodic.

Properties

regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...

is star-free if and only if it is accepted by an automaton with a finite and aperiodic

. This result of algebraic

automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο� ...

is due to

Marcel-Paul Schützenberger Marcel-Paul "Marco" Schützenberger (24 October 1920 – 29 July 1996) was a French mathematician and Doctor of Medicine. He worked in the fields of formal language, combinatorics, and information theory.Herbert Wilf, Dominique Foata, ''et al.' ...

. 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 which 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''^''m''''z'' in ''L'' if and only if ''xy''^''n''''z'' in ''L''. 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.

References

* * — An intensive examination of McNaughton, Papert (1971). * — Uses

Green's relations In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951 ...

to prove Schützenberger's and other theorems. Finite automata {{comp-sci-theory-stub