$A$ is a finite alphabet. $A^*$ is the set of finite words or the free monoid generated by A.

$A^w$ is the set of infinite words generated by A. Denote $A^\infty=A^*\bigcup A^w$.

$X$ is a set of $A^\infty$. Denote $X_{*}=X\bigcap A^*$, $X_w=X\bigcap A^w$.

A binoid over $A$ is a subset $M$ of $A^\infty$ such that $$M_* M\subseteq M,\quad (M_*)^w\subseteq M.$$ The product of two elements is just using concatenation to put them together.

The notation and definition above quote from Algebraic Combinatorics on Words (2002), which is written by M.Lothaire.

It seems that if M is a binoid, $M_*$ must be a subsemigroup of $A^*$. But the book also mentioned that such $M_*$ is also a submonoid of $A^*$.

My question is how to ensure the empty word or so-called unit belongs to $M_*$, such that $M_*$ is not only a subsemigroup, but also a submonoid of $A^*$.

Thanks in advance.

  • $\begingroup$ I don't see how it does. If you take $M = A^{\omega}-\{\text{emptyword}\}$, then it would seem to me that $M$ is a binoid. $\endgroup$ – Arturo Magidin Mar 2 '12 at 6:04
  • $\begingroup$ @ Arturo Magidin :I agree that $M=A^ω−${emptyword}.So I don't konw how $M_*$ comes to be submonoid. $\endgroup$ – Andylang Mar 2 '12 at 7:54

Lothaire goes on to define, for $X\subseteq A^\infty$, $X^\infty\triangleq X_*^\infty\cup(X_*)^*X_\omega=X_*\,^*\cup X_*\,^\omega\cup(X_*)^*X_\omega$ and to say that $M\subseteq A^\infty$ is a binoid iff $M^\infty=M$. Clearly $\varepsilon\in X_*\,^*\subseteq X^\infty$ for all $X\subseteq A^\infty$, so he really does expect a binoid to contain $\varepsilon$ (the empty word).

Equally clearly, $M^\infty=M$ does not follow from $M_*M\subseteq M$ and $(M_*)^\omega\subseteq M$: let $M=\{a^\omega\}$ for some $a\in A$, and note that $M_*=\varnothing$, whence $M_*M=(M_*)^\omega=\varnothing\subseteq M$. Indeed, any non-empty $M\subseteq A^\omega$ would work for the same reason, and Arturo’s example, $M=A^+\cup A^\omega$, also works: $M_*M=A^+(A^+\cup A^\omega)=AA^+\cup A^\omega$ and $(M_*)^\omega=(A^+)^\omega=A^\omega$ are plainly subsets of $M$.

It appears to me that the simplest way to salvage the definition is to require that $M_*M=M$ and $(M_*)^\omega\subseteq M$, thereby forcing $\varepsilon$ to belong to $M_*$; the weaker requirement in the book may simply be a typo.

  • $\begingroup$ @ Brian M. Scott:As what you explained above,the reason for why $ε$ belongs to M is $M^\infty =M$,which implies $M_* ^*$⊆M.Yes?If I fix the definition as $M_* M=M$,I can just make sure the iff condition does hold.But it seems that I still can't get $ε$ belong to M,if I just follow the definition of binoid which is fixed as above. $\endgroup$ – Andylang Mar 2 '12 at 11:22
  • $\begingroup$ @ Brian M. Scott:And the book implied that $M_*$ is a submonoid a little earlier than the iff condition appears. $\endgroup$ – Andylang Mar 2 '12 at 11:25
  • $\begingroup$ @Andylang: I agree: the conditions $M_* M\subseteq M$ and $(M_*)^\omega\subseteq M$ don’t imply that $\varepsilon\in M$. But replacing $M_* M\subseteq M$ with $M_* M=M$ does, and also implies that $M^\infty=M$, which is pretty clearly what he really wants. $\endgroup$ – Brian M. Scott Mar 2 '12 at 11:33
  • $\begingroup$ @ Brian M. Scott: Finally,I completely get your point and agree with you.I think I have no problem now.Thank you for your guiding! $\endgroup$ – Andylang Mar 2 '12 at 14:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.