Mikołaj Bojańczyk

In this page, we show the implication from aperiodic monoids to star-free expressions in the Schützenberger theorem. The implication is stated in the following lemma.

**Lemma 0. **Let be a morphism into a finite aperiodic monoid. Then for every , the inverse image is definable by a star-free expression.

The rest of this page is devoted to proving the above lemma. Fix the morphism as in the lemma. Let us use the name *type of *for the image . Stated in this terminology, we need to show that for every in the monoid, the set of words of type is definable by a star-free expression. The proof is by induction on the position of in the -ordering, with simpler -classes coming first in the induction. (Recall that simpler -classes are those of infixes, in particular the simplest -class is the one that contains the monoid identity.)* *

**Induction base. **The induction base is the case when belongs to the simplest -class, namely the one which contains the identity. By Lemma 4 in the section on Green’s relations, the -class of the identity is a group. Since aperiodic monoids cannot contain non-trivial groups, it follows that the -class of the identity consists only of the identity. This means that the type of a word is the identity if and only if every letter used by that word has the identity type. In other words, the words whose type is the identity are defined by the star-free expression

where is those letters in the alphabet that have non-identity type.

**Induction step. ** Fix some -class in the monoid, and assume that the inverse image is star-free for every which has a -class strictly simpler than . We will now prove that the same holds for every .

Recall that an -class is an intersection of an -class and an -class.

**Lemma 2. **In an aperiodic monoid, every -class has one element.

**Proof. **Stated differently, the lemma says that if are both – and -equivalent, then they are equal. Let be such elements, i.e. there exist some in the monoid such that

Therefore is when and is when . If is large enough, then aperiodicity says that and therefore .

Define to be the set of words which have a prefix whose type is -equivalent to . Likewise define to be the set of words which have a suffix whose type is -equivalent to . Clearly every word with type belongs to both and .

**Lemma 3. **For every , the languages and are star-free.

**Proof. ** We only do the proof for . For a word , consider the shortest prefix that has the same -class as . This prefix exists by membership in , and because the -class of a monoid element is included in its -class. The shortest prefix is nonempty, because is not -equivalent to the identity, and therefore this prefix has to be of the form with having a type that is strictly -simpler than . From the Eggbox Lemma in the section on Green’s relations it follows that the type of is -equivalent to . From these observations, it follows that

where the union ranges over that are strictly -simpler than and letters such that is -equivalent to . The above is definable by a star-free expression, since the induction assumption can be applied to yield star-free expressions for the languages .

The following lemma completes the induction step in the proof of Lemma 0.

**Lemma 4. **For every , the set of words with type is equal to

where the union ranges over such that is -equivalent to but is not.

**Proof. **Let us begin with the left-to-right inclusion. If has type , then it clearly belongs to both and . We need to show that does not belong to the union in the expression from the statement of the lemma. In other words, we need to show that there is no infix of which is of the form such that the type of is -equivalent to some such that is -equivalent to but is not. If there was such an infix, then the type of could be decomposed as for some in the monoid, and therefore would be strictly -simpler than the type of , and therefore the type of would be in a different -class than . This completes the proof of the left-to-right inclusion in the lemma.

Let us do the right-to-left inclusion. Suppose that belongs to the expression in the statement of the lemma. Membership of in and says that the type of is a prefix and suffix of . Therefore, by the Eggbox Lemma, if we prove that the type of of is -equivalent to , we will know that the type of is in the same -class as , and therefore it must be equal to by Lemma 2. So it remains to show that the type of is in . But if were strictly -simpler than the type of , then the shortest prefix with type not -simpler than would belong to as in the statement of the lemma.

## Leave a Reply