Accueil🇫🇷Chercher

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[1]. 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 un groupe de type fini, donné par une présentation 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 tel que engendre . Soit , où est une copie disjointe de ; alors s'étend en un morphisme de monoïde surjectif du monoïde libre sur . Le problème du mot consiste alors à déterminer si , ou bien si pour deux mots et , et où est l'inverse formel de dans et où est l'élément neutre de . De manière équivalente, le problème est de décider si pour un mot de , donc si appartient au langage formel

.

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

Groupe virtuellement libre

Un groupe est virtuellement libre si 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é est virtuellement libre si et seulement si se factorise comme groupe fondamental d'un graphe de groupes[2] - [3].

Groupe context-free

Un groupe est dit « context-free »[4] 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[5] :

Théorème Soit un groupe de type fini avec ensemble de générateurs . Alors est virtuellement libre si et seulement si son problème du mot 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[6] - [7] - [5]. Une introduction détaillée est le texte du mini-cours de Diekert et Weiß[3].
  • 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 est un langage rationnel si et seulement si le groupe G est fini[8].
  • 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[9]. 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[10]. Ultérieurement, Kuske et Lohrey[11] 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.
  • 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[13].
  • Une extension du théorème de Muller–Schupp par Brough [14] 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

  1. David E. Muller, et Paul E. Schupp, « Groups, the theory of ends, and context-free languages », Journal of Computer and System Sciences, vol. 26, no 3, , p. 295-310 (lire en ligne).
  2. A. Karrass, A. Pietrowski et D. Solitar, « Finite and infinite cyclic extensions of free groups », Société mathématique australienne, vol. 16, no 04, , p. 458 (ISSN 1446-7887, DOI 10.1017/S1446788700015445)
  3. Volker Diekert et Armin Weiß, « Context-Free Groups and Bass-Serre Theory », Summer School on Automorphisms of Free Groups, 25-29 septembre 2012 (arXiv 1307.8297)
  4. Le terme « context-free » est en général traduit par « algébrique » en français, mais le mot groupe algébrique désigne un autre objet en mathématiques.
  5. Volker Diekert et Armin Weiß, « Context-free groups and their structure trees », International Journal of Algebra and Computation, vol. 23, no 03, , p. 611–642 (ISSN 0218-1967, DOI 10.1142/S0218196713500124, arXiv 1202.3276)
  6. Yago Antolín, « On Cayley graphs of virtually free groups », Groups, Complexity, Cryptology, vol. 3, no 2, , p. 301-327 (MR 2898895).
  7. T. Ceccherini-Silberstein, and W. Woess, Context-free pairs of groups I: Context-free pairs and graphs. European Journal of Combinatorics 33 (2012), no. 7, 1449-1466
  8. (ru) Anatoly V. Anisimov, « The group languages », Kibernetika (Kiev), vol. 4, , p. 18-24 (MR 301981).
  9. David E. Muller et Paul E. Schupp, « The theory of ends, pushdown automata, and second-order logic », Theoretical Computer Science, vol. 37, no 1, , p. 51–75 (ISSN 0304-3975, DOI 10.1016/0304-3975(85)90087-8).
  10. Michael O. Rabin, « Decidability of second-order theories and automata on infinite trees », Transactions of the American Mathematical Society, vol. 141, , p. 1-35 (lire en ligne).
  11. Dietrich Kuske et Markus Lohrey, « Logical aspects of Cayley-graphs: the group case », Annals of Pure and Applied Logic, vol. 131, nos 1-3, , p. 263-286 (ISSN 0168-0072, DOI 10.1016/j.apal.2004.06.002).
  12. Géraud Sénizergues, « On the finite subgroups of a context-free group », dans Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), American Mathematical Society, Providence, RI,, coll. « DIMACS Ser. Discrete Math. Theoret. Comput. Sci. » (no 25), , p. 201-212
  13. R. H. Gilman, S. Hermiller, D. Holt et S. Rees, « A characterisation of virtually free groups », Archiv der Mathematik, vol. 89, no 4, , p. 289-295.
  14. T. Brough, « Groups with poly-context-free word problem », Groups, Complexity, Cryptology, vol. 6, no 1, , p. 9-29.

Articles connexes

Lien externe

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.