1
$\begingroup$

$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.

  • 0
    @ Arturo Magidin :I agree that $M=A^ω−${emptyword}.So I don't konw how $M_*$ comes to be submonoid.2012-03-02

1 Answers 1

1

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.

  • 0
    @ 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!2012-03-02