An aperiodic finite-state automaton (also called a counter-free automaton) is a finite-state automaton 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' ...

aperiodic A periodic function is a function that repeats its values at regular intervals. For example, the trigonometric functions, which repeat at intervals of 2\pi radians, are periodic functions. Periodic functions are used throughout science to desc ...

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 19 ...

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