Munn tree

Let $X$ be a finite set, and ${\left(X\coprod X^{-1}\right)}^{\ast }$ the free monoid with involution on $X$. It is well known that the elements of ${\left(X\coprod X^{-1}\right)}^{\ast }$ can be viewed as words on the alphabet $\left(X\coprod X^{-1}\right)$, i.e. as elements of the free monod on $\left(X\coprod X^{-1}\right)$.

The Munn tree of the word $w\in {\left(X\coprod X^{-1}\right)}^{\ast }$ is the $X$-inverse word graph $\mathrm{MT}(w)$ (or ${\mathrm{MT}}_X(w)$ if $X$ needs to be specified) with vertex and edge set respectively

$$\mathrm{V}(\mathrm{MT}(w))=\mathrm{red}(\mathrm{pref}(w))=\{\mathrm{red}(v)|v\in \mathrm{pref}(w)\},$$

$$\mathrm{E}(\mathrm{MT}(w))=\{(v,x,\mathrm{red}(vx))\in \mathrm{V}(\mathrm{MT}(w))\times (X\coprod X^{-1})\times \mathrm{V}(\mathrm{MT}(w))\}.$$

The concept of Munn tree was created to investigate the structure of the free inverse monoid. The main result about it says that it “recognize” whether or not two different word in ${\left(X\coprod X^{-1}\right)}^{\ast }$ belong to the same ${\rho }_X$-class, where ${\rho }_X$ is the Wagner congruence on $X$. We recall that if $w\in {\left(X\coprod X^{-1}\right)}^{\ast }$ [resp. $w\in {\left(X\coprod X^{-1}\right)}^{+}$], then ${[w]}_{{\rho }_X}\in \mathrm{FIM}(X)$ [resp. ${[w]}_{{\rho }_X}\in \mathrm{FIS}(X)$].

Theorem 1 (Munn)

Let $v\mathrm{,}w\mathrm{\in }{\mathrm{\left(}X\mathrm{\coprod }{X}^{\mathrm{-}\mathrm{1}}\mathrm{\right)}}^{\mathrm{\ast }}$ (or $v\mathrm{,}w\mathrm{\in }{\mathrm{\left(}X\mathrm{\coprod }{X}^{\mathrm{-}\mathrm{1}}\mathrm{\right)}}^{\mathrm{+}}$). Then ${\mathrm{[}v\mathrm{]}}_{{\rho }_X}\mathrm{=}{\mathrm{[}w\mathrm{]}}_{{\rho }_X}$ if and only if $\mathrm{MT}\mathit{}\mathrm{(}v\mathrm{)}\mathrm{=}\mathrm{MT}\mathit{}\mathrm{(}w\mathrm{)}$

As an immediate corollary of this result we obtain that the word problem in the free inverse monoid (and in the free inverse semigroup) is decidable. In fact, we can effectively build the Munn tree of an arbitrary word in ${\left(X\coprod X^{-1}\right)}^{\ast }$, and this suffice to prove wheter or not two words belong to the same ${\rho }_X$-class.

The Munn tree reveals also some property of the $ℛ$-classes of elements of the free inverse monoid, where $ℛ$ is the right Green relation. In fact, the following result says that “essentially” the Munn tree of $w\in {\left(X\coprod X^{-1}\right)}^{\ast }$ is the Schützenberger graph of the $ℛ$-class of ${[w]}_{{\rho }_X}$.

Theorem 2

Let $w\mathrm{\in }{\mathrm{\left(}X\mathrm{\coprod }{X}^{\mathrm{-}\mathrm{1}}\mathrm{\right)}}^{\mathrm{\ast }}$. There exists an isomorphism (in the category of $X$-inverse word graphs) $\mathrm{\Phi }\mathrm{:}\mathrm{MT}\mathit{}\mathrm{(}w\mathrm{)}\mathrm{\to }\mathrm{S}\mathit{}\mathrm{\Gamma }\mathit{}\mathrm{(}X\mathrm{;}\mathrm{\varnothing }\mathrm{;}{\mathrm{[}w\mathrm{]}}_{{\rho }_X}\mathrm{)}$ between the Munn tree $\mathrm{MT}\mathit{}\mathrm{(}w\mathrm{)}$ and the Schützenberger graph $\mathrm{S}\mathit{}\mathrm{\Gamma }\mathit{}\mathrm{(}X\mathrm{;}\mathrm{\varnothing }\mathrm{;}{\mathrm{[}w\mathrm{]}}_{{\rho }_X}\mathrm{)}$ given by

$${\mathrm{\Phi }}_{\mathrm{V}}(v)={[v]}_{{\rho }_X},\forall v\in \mathrm{V}(\mathrm{MT}(w))=\mathrm{red}(\mathrm{pref}(w)),$$

$${\mathrm{\Phi }}_{\mathrm{E}}((v,x,\mathrm{red}(vx)))=({[v]}_{{\rho }_X},x,{[vx]}_{{\rho }_X}),\forall (v,x,\mathrm{red}(vx))\in \mathrm{E}(\mathrm{MT}(w)).$$