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 1974L'article de 1973 dans Semigroup Forum est un , sans démonstrations ; l'article de 1974 est complet..
Demi-groupe inversif libre Soit un ensemble, soit un ensemble disjoint de et en bijection avec . Soit . La bijection de sur s'étend en un automorphisme involutif du demi-groupe libre engendré par en posant d'abord pour dans , puis en posant pour des mots non vides de , par récurrence sur la longueur des mots.
Le demi-groupe inversif libre sur est le quotient de par la congruence de demi-groupe (la congruence de Wagner) engendrée par les relations pour pour . Ce quotient est noté .
Arbre de Munn
La définition des arbres de Munn fait appel à la réduction au sens des groupes libres : pour de , on note le mot réduit de obtenu en supprimant toutes les occurrences de et , pour dans , qui figurent dans , et en itérant ce procédé si nécessaire. Par exemple, pour le mot réduit de est .
L'arbre de Munn d'un mot de est un graphe dont les sommets sont des mots réduits, et les arcs sont étiquetés par des lettres dans . Les sommets de sont les mots réduits des préfixes de . Les arcs de sont les triplets , où et sont des sommets, est une lettre, et . On écrit plus fréquemment pour ce triplet.
Dit de manière plus compacteComme c'est décrit par exemple dans ou , l'arbre ) est la sous-graphe du graphe de Cayley du groupe libre engendré par induit par .
Exemple vignette|Arbre de Munn du mot . Soit et soit . Les préfixes réduits de sont (calculés de la gauche vers la droite) : . L'arbre de Munn de est donné ci-dessous. On ne trace que des arcs dont l'étiquette est dans , en supposant implicitement un arc en sens inverse étiqueté par la lettre correspondante de .
Considérons le mot . Les préfixes réduits de v sont (calculés de la gauche vers la droite) : . Ce sont les mêmes que pour le mot précédent, les deux mots et définissent en fait le même arbre de Munn, et de plus . Propriétés 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.
Littérature
Notes et références
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.
Catégorie:Algèbre générale