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^[1].

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

yy^{-1}y\sim y

pour

y\in Y^{+}

xx^{-1}yy^{-1}\sim yy^{-1}xx^{-1}

pour

x,y\in Y^{+}

Ce quotient est noté ${\mathit {FI}}(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 $\operatorname {red} (w)$ le mot réduit de $w$ obtenu en supprimant toutes les occurrences de $xx^{-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=aaa^{-1}a^{-1}a^{-1}ab$ est $\operatorname {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=\operatorname {red} (uy)$ . On écrit plus fréquemment $u{\xrightarrow {y}}v$ pour ce triplet.

Dit de manière plus compacte^[2], 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=aaa^{-1}a^{-1}a^{-1}abb^{-1}ab^{-1}bcaa^{-1}cc^{-1}$ .

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

Soit $X=\{a,b,c\}$ et soit $w=aaa^{-1}a^{-1}a^{-1}abb^{-1}ab^{-1}bcaa^{-1}cc^{-1}$ . Les préfixes réduits de $w$ sont (calculés de la gauche vers la droite) : $\varepsilon ,a,aa,a^{-1},b,ab^{-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}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) : $\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 $w$ et $v$ définissent en fait le même arbre de Munn, et de plus $\operatorname {red} (w)=\operatorname {red} (v)=ac$ .

Propriétés

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

Théorème (Munn) — Soient $u$ et $v$ deux mots de $Y^{+}$ . Alors $u\sim v$ si et seulement $T(u)=T(v)$ et $\operatorname {red} (u)=\operatorname {red} (v)$ . En d'autres termes, les mots $u$ et $v$ représentent le même élément du demi-groupe inversif libre si et seulement s'ils ont même arbre de Munn et si leurs chemins dans l'arbre de Munn mène au même sommet.

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

Littérature

(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)

Notes et références

↑ L'article de 1973 dans Semigroup Forum est un « reseach announcement », sans démonstrations ; l'article de 1974 est complet.
↑ Comme c'est décrit par exemple dans (Margolis, Meakin (1993a)) ou (Margolis, Meakin (1993b))

Voir aussi

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.