Arbre de Munn

Un arbre de Munn est un arbre associé à un élément d'un demi-groupe inversif libre. La correspondance entre arbres et éléments du demi-groupe est bijective. Elle permet notamment de décider de l'égalité de deux éléments du demi-groupe, et ainsi de résoudre le problème du mot dans le demi-groupe inversif libre. D'autres propriétés du demi-groupe s'expriment combinatoirement dans ces arbres. Les arbres de Munn portent le nom de leur inventeur qui les a annoncés en 1973 et présentés en 1974.

Demi-groupe inversif libre

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

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

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

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

Ce quotient est noté $𝐹𝐼(X)$.

Arbre de Munn

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

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

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

Exemple

Arbre de Munn du mot $w=aa{a}^{-1}{a}^{-1}{a}^{-1}ab{b}^{-1}a{b}^{-1}bca{a}^{-1}c{c}^{-1}$.

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

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

Propriétés

La propriété principale des arbres de Munn est la suivante : Modèle:Théorème

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

Littérature

• Modèle:Ouvrage

• Modèle:Article

• Modèle:Article

• Modèle:Article

• Modèle:Article

• Modèle:Article

Voir aussi

Articles connexes

• demi-groupe inversif
• Walter D. Munn

Liens externes

• Marco Mazzucchelli. "Munn tree" (version 17). PlanetMath.org. Freely available at http://planetmath.org/encyclopedia/MunnTree.html
• Marco Mazzucchelli. "example of Munn tree" (version 17). PlanetMath.org. Freely available at http://planetmath.org/ExampleOfMunnTree.html.