Arbre de Munn

élément mathématique

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

modifier

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

modifier

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 compacte[2], l'arbre  ) est la sous-graphe du graphe de Cayley du groupe libre engendré par   induit par  .

Exemple

modifier
 
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

modifier

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

Théorème (Munn) — Soient   et   deux mots de  . Alors   si et seulement   et  . En d'autres termes, les mots   et   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

modifier
  • (en) M. V. Lawson, Inverse Semigroups : The Theory of Partial Symmetries, World Scientific,
  • (en) Stuart W. Margolis et John C. Meakin, « Inverse monoids, trees and context-free languages », Trans. Amer. Math. Soc., vol. 335, no 1,‎ , 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, no 1,‎ , p. 79-99 (MR 94c:20105)
  • (en) Walter Douglas Munn, « Free inverse semi-groups », Proceedings of the London Mathematical Society. Third Series, vol. 29,‎ , p. 385-404 (DOI 10.1112/plms/s3-29.3.385, MR 0360881)
  • Viktor V. Wagner, « Generalised groups », Doklady Akademii Nauk SSSR, vol. 84,‎ , p. 1119–1122 (lire en ligne)

Notes et références

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

Voir aussi

modifier

Articles connexes

modifier

Liens externes

modifier