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