Théorème de Muller-Schupp

En mathématiques et en informatique théorique, le théorème de Muller-Schupp affirme qu'un groupe G de type fini possède un problème du mot pour les groupes qui est un langage algébrique si et seulement s'il est virtuellement libre. Le théorème a été démontré pour la première fois par David E. Muller et Paul E. Schupp en 1983. Depuis, d'autres démonstrations ont été données.

Le théorème

Problème du mot pour les groupes

Le problème du mot pour un groupe de type fini G est le problème algorithmique de décider si deux mots en les générateurs représentent le même élément. Soit $G$ un groupe de type fini, donné par une présentation $G=\langle X\mid R\rangle$ avec X fini. Plus précisément, si X un ensemble fini de générateurs pour G, alors le problème du mot est le problème algorithmique de l’appartenance d'un mot sur X et sur ses inverses au langage formel qui est constitué des mots sur X et son ensemble d'inverses formels qui sont envoyés par l'application naturelle sur l'identité du groupe G. On considère X comme un alphabet, muni d'un morphisme $\pi :X\to G$ tel que $\pi (X)\subseteq G$ engendre $G$. Soit $\Sigma _{X}=X\sqcup X^{-1}$, où $X^{-1}$ est une copie disjointe de $X$ ; alors $\pi :X\to G$ s'étend en un morphisme de monoïde surjectif du monoïde libre $\Sigma _{X}^{*}$ sur $G$. Le problème du mot consiste alors à déterminer si $\pi (u)=\pi (v)$, ou bien si $\pi (uv^{-1})=e$ pour deux mots $u$ et $v$, et où $v^{-1}$ est l'inverse formel de $v$ dans $\Sigma _{X}^{*}$ et où $e$ est l'élément neutre de $G$ . De manière équivalente, le problème est de décider si $\pi (x)=e$ pour un mot $x$ de $\Sigma _{X}^{*}$, donc si $x$ appartient au langage formel

${\mathcal {W}}(G,X)=\{w\in \Sigma _{X}^{*}\mid \pi (w)=e\}$.

Par un raccourci un peu elliptique, on dit aussi que l'ensemble ${\mathcal {W}}(G,X)$ est le problème du mot de $G$ par rapport à X. On dit aussi que le problème du mot est résoluble si l'appartenance au langage ${\mathcal {W}}(G,X)$ est décidable.

Groupe virtuellement libre

Un groupe $G$ est virtuellement libre si $G$ possède un sous-groupe libre d'index fini. Un résultat de base dans la théorie de Bass-Serre (en) dit qu'un groupe finiment engendré $G$ est virtuellement libre si et seulement si $G$ se factorise comme groupe fondamental d'un graphe de groupes .

Groupe context-free

Un groupe $G$ est dit « context-free » si son problème de mot est un langage algébrique (« context-free »).

Énoncé du théorème

Le théorème s'énonce comme suit :

Théorème — Soit $G$ un groupe de type fini avec ensemble de générateurs $X$. Alors $G$ est virtuellement libre si et seulement si son problème du mot ${\mathcal {W}}(G,X)$ est un langage algébrique.

Une formulation équivalente est :

Formulation équivalente — Un groupe de type fini est context-free si et seulement s'il est virtuellement libre.

Autres preuves

• Depuis l'article de 1983, plusieurs autres preuves du théorème de Muller–Schupp ont été données. Une introduction détaillée est le texte du mini-cours de Diekert et Weiß.
• Le théorème de Muller-Schupp est une généralisation considérable d'un théorème d'Anisimov de 1971 qui statue que, pour un groupe de type fini G avec un ensemble générateur fini X, le problème du mot ${\mathcal {W}}(G,X)$ est un langage rationnel si et seulement si le groupe G est fini.
• Le théorème, dans sa formulation de l'article de 1983, est moins général parce qu'il utilise la notion d'accessibilité pour des groupes de type fini ; l'énoncé original dit qu'un groupe est virtuellement libre si et seulement s'il est accessible et son problème du mot est un langage algébrique. Depuis, cette hypothèse supplémentaire a pu être levée.

Applications

• Dans un autre article, Muller et Schupp démontrent qu'un graphe finiment engendré Γ n'a qu'un nombre fini de types d'isomorphie de bouts si et seulement si Γ est le graphe des transitions d'un automate à pile. Comme conséquence, ils montrent que la logique monadique du second ordre d'un graphe context-free (comme le graphe de Cayley d'un groupe virtuellement libre) est décidable, ce qui généralise le théorème de Rabin sur les arbres binaires. Ultérieurement, Kuske et Lohrey ont montré que les groupes virtuellement libres sont les seuls groupes de type fini dont les graphes de Cayley ont une théorie monadique décidable.

• Géraud Sénizergues utilise le théorème de Muller–Schupp pour démontrer que le problème d'isomorphisme de groupes (en) est primitif récursif pour les groupes virtuellement libres de type fini.

• Gilman, Hermiller, Holt et Rees utilisent le théorème de Muller–Schupp pour démonter qu'un groupe de type fini est virtuellement libre s'il existe un ensemble fini de règles de réécriture décroissantes en longueur pour un ensemble de générateurs X dont l'application itérée réduit tout mot en un mot géodésique.

• Une extension du théorème de Muller–Schupp par Brough considère des groupes dont le problème du mot est une intersection d'un nombre fini de langage algébriques.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Muller–Schupp theorem » (voir la liste des auteurs).

Articles connexes

• Automate d'arbres
• Problème du mot
• Langage formel

Lien externe

• Armin Weiß, « Context-free groups and their structure trees » — Transparents d'un exposé, 2013.