Schützenberger's theorem on star-free languages

Remarks

For a finite monoid, being aperiodic is equivalent to having only trivial subgroups. The easier direction shows by induction on the star-free construction that the syntactic monoids stay aperiodic; the key case is concatenation. The harder direction builds a star-free expression for each preimage of an element of an aperiodic monoid, by induction on the ideal structure of the monoid. Example: $(aa)^*$ over $\set{a}$ has syntactic monoid $\Z/2\Z$, in which $x^n \ne x^{n+1}$ for the generator and every $n$, so it is not star-free. In contrast, $(ab)^*$ over $\set{a, b}$ has an aperiodic syntactic monoid with six elements, and indeed it is star-free. Since the syntactic monoid of a regular language is computable and finite, the theorem gives an algorithm to decide whether a regular language is star-free.

Going deeper

For a student

This is the first and most famous instance of the algebraic classification of regular languages, which matches varieties of finite monoids with classes of languages. Together with the theorem of McNaughton and Papert, it shows that three classes coincide: star-free languages, languages definable in first-order logic over words, and languages with aperiodic syntactic monoid. Kamp's theorem adds linear temporal logic to this list, which is why the result matters in program verification.