I am following the proof of Lemma 7 of this document.

Lemma 7. If $L=h^{-1}(I)$ for some ideal $I$ in the monoid $M$, then $L$ can be expressed using star-free expressions involving languages which are recognized by smaller aperiodic monoids.

The idea of the proof is simple enough to follow, although it is not very well written. However, I don't see the reasoning behind the first part of paragraph 8 of the proof:

Consider $h(a)y$. If $h(a)y\notin F(y)$, then there must be $p,q$ such that $y=ph(a)yq$. Thus, $y=ph(a)y$ and $\dots$

I'm struggling to understand how we can infer that $y=ph(a)y$ from $y=ph(a)yq$, even if we consider $M$ to be aperiodic. That's my question. I might be missing something trivial, but I'm missing it anyway. Thanks in advance if you can read the document and help me. In any case, I am providing some context:

Context: Schützenberger's theorem

Consider a finite alphabet $A$ and the free monoid $A^*$ over this alphabet. A language is a subset of $A^*$. Now consider regular expressions with concatenation ($r_1r_2$), union ($r_1+r_2$) and complement ($\overline{r_1}$). We do not consider the star operator ($r_1^*$). These are called star-free expressions.

A monoid $M$ is aperiodic if it contains no non-trivial subgroup, or equivalently, if for all $x\in M$ there is $n\in\mathbb{N}$ such that $x^{n+1}=x^n$. The syntactic monoid of a language $L$ is the quotient $A^*/\sim_L$, where $\sim_L$ is the following equivalence relation: $x\sim_Ly$ if for all $u,v\in A^*$, $uxv\in L\Leftrightarrow uyv\in L$.

Schützenberger's theorem states that a language is star-free if and only if its syntactic monoid is finite and aperiodic.

For an element $y$ in a monoid $M$, $F(y)$ is the forbidding ideal of $y$, that is the set of elements that cannot divide $y$ (cannot generate $y$ via multiplication):

$F(y)=\{x\in M\mid pxq\neq y\text{ for all } p,q\in M\}$

The monoid homomorphism we are considering is $h:A^*\to M$. Here, $L\subset A^*$ is recognized by the ideal $I\subset M$ (that is, if $L=h^{-1}(I)$).

In the proof, we take an arbitrary word $w\in L$ and consider a minimal substring $u$ of $w$ that is in $L$. The hard case is when $|u|>1$, that is, when $u=avb$ for some $a,b\in A$ and $v\in A^*$. We denote $y=h(v)$ and now we consider the forbidding ideal $F(y)$.

We have to show that $F(y)$ has at least two elements. First we show that there is at least one element in $F(y)\cap I$, and now we try to show there's one element in $F(y)\smallsetminus I$. For this, the author considers $h(a)y$ and tries to contradict the minimality of $u$, and this is the part of the proof I don't follow.

  • 2
    $\begingroup$ It looks to me as if $M$ is assumed to be aperiodic, so that Lemma 2 applies. $\endgroup$ – Brian M. Scott Nov 10 '11 at 15:59
  • $\begingroup$ @BrianM.Scott apparently, $M$ being aperiodic is what's missing in the statement. Indeed it was something trivial, thanks for the observation! And I'm guessing it doesn't work for an arbitrary monoid, right? $\endgroup$ – Janoma Nov 10 '11 at 16:07
  • $\begingroup$ I’d be astonished if it did. Certainly it’s not true in general that if $x=axb$, then $x=ax$. $\endgroup$ – Brian M. Scott Nov 10 '11 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.