Les représentations du monoïde H+

Télécharger le fichier original (Mémoire de fin d’études)

Le monoïde H+

Dans ce chapitre introductif, on rappelle le contexte général des monoïdes présentés, et, en particulier, le cas des monoïdes de tresses et de Thompson, et on introduit le monoïde H+ qui est notre principal sujet d’étude. Après la définition, on établit quelques premières propriétés.
Ce chapitre comporte trois sections. Dans la section 1, on rappelle le contexte général des monoïdes présentés, et on introduit les notions classiques liées aux relations de divisibilité, en particulier les notions de pgcd et de ppcm, et celle de monoïde noethéorien.
Dans la section 2, on introduit les deux principaux monoïdes qui forment le contexte de cette étude, à savoir le monoïde des tresses B1+ et le monoïde de Thompson F +. On présente également le monoïde des tresses parenthé-d+ sées BV , qui est un hybride des deux précédents, en l’occurrence un produit de Zappa-Szep.
Enfin, dans la section 3, on introduit le monoïde H+ objet de la thèse, par une présentation qui en fait un (autre) hybride des monoïdes B1+ et F +, et on établit quelques propriétés qui dérivent directement de la présentation, en particulier la noethérianité et la décidabilité du problème de mots. On observe également que le monoïde de Thompson F + est un quotient propre de H+.

Généralités sur les monoïdes

Monoïdes présentés. On rappelle ici les notions et notations standards concernant les monoïdes

libres et les présentations de monoïde.
Le point de départ est la notion de mot sur un alphabet.
Définition 1.1 (mot, concaténation). (i) Si S est un ensemble non vide (« alphabet »), un S-mot est une suite finie w d’éléments de S, c’est-à-dire une application d’un intervalle f1; :::; ‘g dans S. L’entier ‘ est appelé la longueur de w, notée jw j. Pour 1 6 i 6 ‘, on note w[i] l’image de i, appelé la i-ème lettre de u. On note » le mot vide, à savoir l’unique fonction de ; dans S, donc est l’ensemble vide ; sa longueur est 0. On note S l’ensemble de tous les mots sur S.
(ii) Si u; v sont deux S-mots de longueurs respectives p et q, on note u v, ou uv, la concaténation de u et v, définie comme le S-mot w de longueur p+q défini par w[i] := u[i] pour 1 6 i 6 p et w[i] := v[i p] pour p+1 6 i 6 p+q. Le résultat suivant est alors classique :
LE MONOïDE H+
Proposition 1.2 (monoïde libre). La structure (S ; ; « ) est un mo-noïde libre de base S. La démonstration de la proposition 1.2 est facile (voir par exemple [28, section I.4], et on ne la redonne pas ici. On rappelle qu’un monoïde M est dit libre de base S si M est engendré par S et si, pour tout monoïde M0 et toute application : S ! M0, il existe un morphisme de monoïde : M ! M0 prolongeant (et qui, de surcroît, est unique). Dans la suite, on note généralement S pour le monoïde (S ; ; « ).
La proposition 1.2 implique que tout monoïde M engendré par un en-semble S est un quotient du monoïde S : il existe une congruence sur S , c’est-à-dire une relation d’équivalence compatible avec la concaténation des mots, telle que M est (isomorphe au) quotient S = .
Lemme 1.3. Pour tout ensemble R de paires d’éléments de S , il existe une plus petite congruence R incluant R.
Démonstration. Soit R la relation binaire sur S telle que w R w0 est vraie s’il existe une suite finie w0; :::; w‘ vérifiant w = w0, w0 = w‘ et, pour
tout i < ‘, il existe des S-mots ui; u0i et fvi; vi0g dans R vérifiant wi = uiviu0i et wi+1 = uivi0u0i.
Alors R est une congruence sur le monoïde S incluant R. D’abord R est réflexive car, pour tout w, la suite (w) témoigne pour w R w. Ensuite, si (w0; :::; w‘) témoigne pour w R w0, alors (w‘; :::; w0) témoigne pour w0 R w. Puis, si (w0; :::; w‘) témoigne pour w R w0 et (w00; :::; w‘00) témoigne pour w0 R w00, alors la suite (w0; :::; w‘; w10; :::; w‘00) témoigne pour w R w00. Donc R est une relation d’équivalence sur S . Par ailleurs, R est une congruence sur le monoïde S : si (w0; :::; w‘) témoigne pour w R w0, alors (uw0v; :::; uw‘v) témoigne pour uwv R uw0v. Enfin, si fv; v0g appartient à R, la suite (v; v0) témoigne pour v R v0, et donc R inclut R — plus
exactement : contient tous les couples (w; w0) tels que la paire f w; w0 g R est dans R.
Supposons que est une congruence sur S incluant R (au sens ci- dessus), et qu’on a w ‘ ) témoignant R w0. Il existe alors une suite (w0; :::; w pour w R w 0. Par définition, pour chaque i, il existe u ; u et f v ; v i0g dans R e i i0 i vérifiant wi = uiviu0 et wi+1 = uiv0u0 . Puisque R est inclus dans et que e > i e i i e est symétrique, on a vi i i i i wi+1, v0, puis uiviu0 uiv0u0 , c’est-à-dire wi puisque est une congruence, et enfin w = w w = w 0 car est transitive 0 ‘ e (pour le cas ‘ 2) et réflexive (pour le cas ‘ = 1). Donc e inclut R, qui est la e e e plus petite congruence incluant R.
Dans le contexte du lemme 1.3, la plus petite congruence incluant R est appelée la congruence engendrée par R. Pour spécifier un monoïde M engendré par un ensemble S, il suﬃt de spécifier la congruence R telle que M est S = R, et donc de spécifier un sous-ensemble R de S S engendrant R.
GÉNÉRALITÉS SUR LES MONOïDES 3
Définition 1.4 (présentation). On appelle présentation de monoïde un couple (S; R), où S est un ensemble non vide et R est un ensemble de paires de mots de S . On note alors hS j Ri+ le monoïde S = R, où R est la congruence sur S engendrée par R. Si u est un S-mot, on note [u] la classe de u par rapport à R.
Quand il n’y a pas de confusion possible, on notera au lieu de R. On sait que, dans le contexte de la définition 1.4, on note généralement « u = v » au lieu de « fu; vg » les relations de R.
Exemple 1.5 (monoïdes libres). Pour tout ensemble S, la congruence sur S engendrée par l’ensemble vide est l’égalité : les seules suites (w0; :::; w‘) témoignant pour une équivalence w R w0 sont les suites triviales (w). Donc le monoïde hS j ;i+ est S ==, c’est-à-dire S .
Exemple 1.6 (monoïdes commutatifs libres). Soit S un ensemble fini à n éléments, disons S = fa1; :::; ang. On pose (1.7) M = hS j faiaj = ajai j i 6= jgi+: Notons la congruence engendrée par les relations de (1.7). Pour décrire M, il suﬃt d’identifier un élément distingué dans chaque classe d’équivalence pour . Soit F l’application de S dans Nn définie par F (w) = (jwja1 ; :::; jwjan );
où jwjai est le nombre d’occurrences de ai dans w. Par définition, on a F (aiaj) = F (ajai) pour tous i; j. Par ailleurs, pour tous mots u; v de S , on a F (uv) = F (u) + F (v), où + est la somme terme à terme sur Nn. Il en résulte que la relation F (w) = F (w0) est un congruence sur S , qui inclut les rela-tions de (1.7). Par conséquent, w w0 implique F (w) = F (w0). Dans l’autre sens, appelons normaux les S-mots du type ae11 aenn avec e1; :::; en > 0. Alors tout S-mot est -équivalent à un mot normal. Si deux S-mots w; w0 vérifient F (w) = F (w0), alors ils sont tous deux -équivalents au même S-mot normal, et donc vérifient w w0. Par conséquent, les relations w w0 et F (w) = F (w0) sont équivalentes. De plus, si w et w0 sont des S-mots normaux distincts, alors, par définition, on a F (w) 6= F (w0). Par conséquent, tout S-mot est -équivalent à un unique S-mot normal, et l’application F induit une bijection entre l’ensemble Snorm des S-mots normaux et l’ensemble Nn.
De plus, on a noté que F (uv) = F (u) + F (v) est vérifié pour tous S-mots u; v, donc la bijection ci-dessus est un isomorphisme entre le monoïde M et le monoïde (Nn; +). En d’autres termes, le monoïde M est (isomorphe à) (Nn; +). Par construction, M est un monoïde commutatif et il engendré par fa1; :::; ang. On peut noter que M est un monoïde commutatif libre de base fa1; :::; ang. En eﬀet, soit M1 un monoïde commutatif quelconque, et soit une application de fa1; :::; ang dans M1. Par définition, M est le quo-tient du monoïde libre S par la congruence . Soit l’unique extension de en un homomorphisme du monoïde libre S dans M1 (lemme 1.2).

Table des matières

Introduction
Le monoïde H+
Principaux résultats
Organisation du texte
Chapitre I. Le monoïde H+
1. Généralités sur les monoïdes
1.1. Monoïdes présentés
1.2. Diviseurs et multiples
1.3. Noethérianité
2. Le contexte
2.1. Le monoïde de tresses positives B+1
2.2. Le monoïde de Thompson F+
2.3. Tresses et permutations parenthésées
3. Le monoïde H+
3.1. Présentation par générateurs et relations
3.2. Paramètres numériques
3.3. Lien avec le monoïde de Thompson
Chapitre II. Utilisation de la réécriture
1. Systèmes de réécriture
1.1. Réécriture associée à une présentation
1.2. Convergence
1.3. Noethérianité et confluence
2. Le cas du monoïde de Thompson
2.1. Le système EF 2.2. Les mots EF -réduits
3. Le cas du monoïde H+
3.1. Le système EH 3.2. Les mots EH-réduits
3.3. Applications
Chapitre III. La méthode du retournement de facteur
1. Le retournement de facteur
1.1. Suites et diagrammes de retournement
1.2. Complétude du retournement
1.3. Terminaison du retournement
2. Un nouveau critère de complétude
2.1. Ensembles clos par complément
2.2. Énoncé principal et exemple
2.3. Démonstration de la proposition III.2.8
3. Un nouveau critère de terminaison
3.1. Les présentations (S0;R0)
3.2. Comparaison des retournements
3.3. Application à la terminaison
Chapitre IV. Utilisation du retournement
1. Principes généraux
1.1. Simplifiabilité
1.2. Multiples communs
1.3. Le problème de mots
2. Le retournement pour H+ : complétude
2.1. La condition du cube à droite
2.2. Applications I : simplifiabilité et ppcm
2.3. Le retournement à gauche
3. Le retournement pour H+ : terminaison
3.1. Un ensemble clos par complément
3.2. Application II : résultats de décidabilité
3.3. Terminaison du retournement à gauche
Appendice : variantes de la présentation
Chapitre V. Les éléments simples de H+
1. Les éléments n
1.1. Le ppcm de 1; ::: ; n􀀀1
1.2. Les diviseurs à gauche de n
2. Dénombrement des éléments simples
2.1. Résultats préparatoires
2.2. Le résultat de partition
2.3. Dénombrement des diviseurs de n
3. Forme normale et décomposition
3.1. Décidabilité de la simplicité
3.2. Le lemme-clé
3.3. Forme normale des éléments simples
4. La structure « presque-Garside » de H+
4.1. Décompositions gloutonnes
4.2. Le cas du monoïde H+
Chapitre VI. Suite et fin
1. Les représentations du monoïde H+
1.1. Représentations géométriques et fonctionnelles
1.2. La représentation S
1.3. Les représentations s;t
2. Des questions ouvertes
2.1. Propriétés des relations de divisibilité
2.2. Le groupe H
2.3. Représentations du monoïde H+ (et du groupe H)
Annexe informatique
1. Représentation des données
2. Principaux algorithmes
2.1. Mise sous forme normale
2.2. Retournement à droite et procédures dérivées
2.3. Comptage des éléments simples
2.4. Représentations linéaires
Bibliographie
Index