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. ${(\mathrm{mgs}(M))}^{\ast }=M$, and

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
Canonical name	FreeSubmonoid
Date of creation	2013-03-22 18:21:36
Last modified on	2013-03-22 18:21:36
Owner	Ziosilvio (18733)
Last modified by	Ziosilvio (18733)
Numerical id	5
Author	Ziosilvio (18733)
Entry type	Definition
Classification	msc 20M10
Classification	msc 20M05
Defines	minimal generating set of a submonoid