Arbre de Munn

Soit ${\displaystyle X}$ un ensemble, soit ${\displaystyle X^{-1}}$ un ensemble disjoint de ${\displaystyle X}$ et en bijection avec ${\displaystyle X}$. Soit ${\displaystyle Y=X\cup X^{-1}}$. La bijection ${\displaystyle x\mapsto x^{-1}}$ de ${\displaystyle X}$ sur ${\displaystyle X^{-1}}$ s'étend en un automorphisme involutif du demi-groupe libre ${\displaystyle Y^{+}}$ engendré par ${\displaystyle Y}$ en posant d'abord ${\displaystyle (x^{-1})^{-1}=x}$ pour ${\displaystyle x^{-1}}$ dans ${\displaystyle X^{-1}}$, puis en posant ${\displaystyle (uv)^{-1}=v^{-1}u^{-1}}$ pour des mots non vides ${\displaystyle u,v}$ de ${\displaystyle Y^{+}}$, par récurrence sur la longueur des mots.

Le demi-groupe inversif libre sur ${\displaystyle X}$ est le quotient de ${\displaystyle Y^{+}}$ par la congruence de demi-groupe (la congruence de Wagner) engendrée par les relations

${\displaystyle yy^{-1}y\sim y}$ pour ${\displaystyle y\in Y^{+}}$

${\displaystyle xx^{-1}yy^{-1}\sim yy^{-1}xx^{-1}}$ pour ${\displaystyle x,y\in Y^{+}}$.

Ce quotient est noté ${\displaystyle {\mathit {FI}}(X)}$.

La définition des arbres de Munn fait appel à la réduction au sens des groupes libres : pour ${\displaystyle w}$ de ${\displaystyle Y^{+}}$, on note ${\displaystyle \operatorname {red} (w)}$ le mot réduit de ${\displaystyle w}$ obtenu en supprimant toutes les occurrences de ${\displaystyle xx^{-1}}$ et ${\displaystyle x^{-1}x}$, pour ${\displaystyle x}$ dans ${\displaystyle X}$, qui figurent dans ${\displaystyle w}$, et en itérant ce procédé si nécessaire. Par exemple, pour ${\displaystyle X=\{a,b,c\}}$ le mot réduit de ${\displaystyle w=aaa^{-1}a^{-1}a^{-1}ab}$ est ${\displaystyle \operatorname {red} (w)=b}$.

L'arbre de Munn ${\displaystyle T(w)}$ d'un mot ${\displaystyle w}$ de ${\displaystyle Y^{+}}$ est un graphe dont les sommets sont des mots réduits, et les arcs sont étiquetés par des lettres dans ${\displaystyle Y}$. Les sommets de ${\displaystyle T(w)}$ sont les mots réduits des préfixes de ${\displaystyle w}$. Les arcs de ${\displaystyle T(w)}$ sont les triplets ${\displaystyle (u,y,v)}$, où ${\displaystyle u}$ et ${\displaystyle v}$ sont des sommets, ${\displaystyle y}$ est une lettre, et ${\displaystyle v=\operatorname {red} (uy)}$. On écrit plus fréquemment ${\displaystyle u{\xrightarrow {y}}v}$ pour ce triplet.

Dit de manière plus compacte[2], l'arbre ${\displaystyle T(w}$) est la sous-graphe du graphe de Cayley du groupe libre engendré par ${\displaystyle X}$ induit par ${\displaystyle w}$.

Arbre de Munn du mot ${\displaystyle w=aaa^{-1}a^{-1}a^{-1}abb^{-1}ab^{-1}bcaa^{-1}cc^{-1}}$.

Soit ${\displaystyle X=\{a,b,c\}}$ et soit ${\displaystyle w=aaa^{-1}a^{-1}a^{-1}abb^{-1}ab^{-1}bcaa^{-1}cc^{-1}}$. Les préfixes réduits de ${\displaystyle w}$ sont (calculés de la gauche vers la droite) : ${\displaystyle \varepsilon ,a,aa,a^{-1},b,ab^{-1},ac,aca,acc}$. L'arbre de Munn de ${\displaystyle w}$ est donné ci-dessous. On ne trace que des arcs dont l'étiquette est dans ${\displaystyle X}$, en supposant implicitement un arc en sens inverse étiqueté par la lettre correspondante de ${\displaystyle X^{-1}}$.

Considérons le mot ${\displaystyle v=a^{-1}abb^{-1}aaa^{-1}b^{-1}bccc^{-1}aa^{-1}}$. Les préfixes réduits de v sont (calculés de la gauche vers la droite) : ${\displaystyle \varepsilon ,a^{-1},b,a,aa,ab^{-1},ac,acc,aca}$. Ce sont les mêmes que pour le mot précédent, les deux mots ${\displaystyle w}$ et ${\displaystyle v}$ définissent en fait le même arbre de Munn, et de plus ${\displaystyle \operatorname {red} (w)=\operatorname {red} (v)=ac}$.

La propriété principale des arbres de Munn est la suivante :

Il en résulte immédiatement que le problème du mot est décidable dans le demi-groupe inversif libre.

• (en) M. V. Lawson, Inverse Semigroups : The Theory of Partial Symmetries, World Scientific, 1998

• (en) Stuart W. Margolis et John C. Meakin, « Inverse monoids, trees and context-free languages », Trans. Amer. Math. Soc., vol. 335, n^o 1,‎ 1993, p. 259-276 (MR 93h:20062)

• (en) Stuart W. Margolis et John C. Meakin, « Free inverse monoids and graph immersions », Internat. J. Algebra Comput., vol. 3, n^o 1,‎ 1993, p. 79-99 (MR 94c:20105)

• (en) Walter Douglas Munn, « Free inverse semi-groups », Semigroup Forum, vol. 5, n^o 1,‎ 1973, p. 262-269 (DOI 10.1007/BF02572897)

• (en) Walter Douglas Munn, « Free inverse semi-groups », Proceedings of the London Mathematical Society. Third Series, vol. 29,‎ 1974, p. 385-404 (DOI 10.1112/plms/s3-29.3.385, MR 0360881)

• Viktor V. Wagner, « Generalised groups », Doklady Akademii Nauk SSSR, vol. 84,‎ 1952, p. 1119–1122 (lire en ligne)