# free submonoid

Let $A$ be an arbitrary set, let $A^{\ast}$ be the free monoid on $A$, and let $e$ be the identity element (empty word) of $A^{\ast}$.

Let $M$ be a submonoid of $A^{\ast}$. The minimal generating set of $M$ is

 $\mathrm{mgs}(M)=(M\setminus\{e\})\setminus(M\setminus\{e\})^{2}\;.$ (1)

Shortly, $\mathrm{mgs}(M)$ is the set of all the nontrivial elements of $M$ that cannot be “reconstructed” as products of elements of $M$. It is straightforward that

1. 1.

$(\mathrm{mgs}(M))^{\ast}=M$, and

2. 2.

if $S\subseteq A^{\ast}$ and $M\subseteq S^{\ast}$, then $\mathrm{mgs}(M)\subseteq S$.

We say that $M$ is a free submonoid of $A^{\ast}$ if it is isomorphic (as a monoid) to a free monoid $B^{\ast}$ for some set $B$. A set $K\subseteq A^{\ast}$ such that $K=\mathrm{mgs}(M)$ for some free submonoid $M$ of $A^{\ast}$ is also called a code.

Title free submonoid FreeSubmonoid 2013-03-22 18:21:36 2013-03-22 18:21:36 Ziosilvio (18733) Ziosilvio (18733) 5 Ziosilvio (18733) Definition msc 20M10 msc 20M05 minimal generating set of a submonoid