Problème du mot pour les groupes

En mathématiques, plus précisément dans le domaine de la théorie combinatoire des 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 du groupe représentent le même élément. Plus précisément, si X un ensemble fini de générateurs pour G, on considère le langage formel 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. Le problème du mot est le problème algorithmique qui consiste à décider de l’appartenance ou non d'un mot à ce langage formel. On peut voir que si Y est un autre ensemble de générateurs pour G, alors le problème du mot avec l'ensemble Y est équivalent au problème du mot avec ensemble X. On peut donc parler sans ambiguïté de la décidabilité du problème du mot pour un groupe G de type fini. Un problème différent mais lié est le problème du mot uniforme pour une classe K de groupes donnés par un ensemble récursif de présentations ; le problème algorithmique est alors de décider, étant donné une présentation P d'un groupe G de la classe K, si deux mots représentent le même élément de G. On peut aussi considérer que la classe K est définissable seulement par un ensemble récursivement énumérable de présentations. Le problème du mot est indécidable dans le cas général, mais est décidable pour de nombreux groupes. Par exemple, les ont un problème du mot décidable ; de même, l'algorithme de Todd-Coxeter et la complétion de Knuth-Bendix donnent des résultats effectifs. D'un autre côté, le fait qu'un algorithme particulier ne s'applique pas dans un cas particulier n'implique pas que le problème du mot est indécidable. Par exemple, l'algorithme de Dehn ne résout pas le problème du mot pour le groupe fondamental du tore, et pourtant ce groupe est le produit direct de deux groupes cycliques infinis et possède donc un problème du mot décidable. On considère une présentation donnée par un couple où est l’ensemble des générateurs et l’ensemble des relateurs.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (1)

Concepts associés (25)

Séances de cours associées (17)

On Polynomial Algorithms for Normalizing Formulas

Viktor Kuncak, Simon Guilloud, Mario Bucev

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms f

2022

Graphe de Cayley

En mathématiques, un graphe de Cayley (du nom d'Arthur Cayley) est un graphe qui encode la structure d'un groupe. C'est un outil important pour l'étude de la combinatoire et de la géométrie des groupes. Étant donné un groupe et une partie génératrice de ce groupe, le graphe de Cayley Cay(G,S) est construit comme suit : À chaque élément de , on associe un sommet . À chaque élément de , on associe une couleur . Pour tout et , on trace une arête orientée de couleur du sommet vers le sommet .

Théorie des groupes

vignette|Le Rubik's cube illustre la notion de groupes de permutations. Voir groupe du Rubik's Cube. La théorie des groupes est en mathématique, plus précisément en algèbre générale, la discipline qui étudie les structures algébriques appelées groupes. Le développement de la théorie des groupes est issu de la théorie des nombres, de la théorie des équations algébriques et de la géométrie. La théorie des groupes est étroitement liée à la théorie des représentations.

Max Dehn

Max Dehn ( – ) est un mathématicien allemand. Il a étudié les fondements de la géométrie avec Hilbert à Göttingen en 1899, et obtenu une preuve du théorème de Jordan pour les polygones. En 1900, il a soutenu sa thèse sur le rôle du dans la géométrie axiomatique. En 1900, il a aussi résolu le troisième problème de Hilbert. Il était en poste de 1900 à 1911 à l'université de Münster. Ses intérêts se tournent ensuite vers la topologie et la théorie combinatoire des groupes.

Explore des groupes plats d'automorphismes et leurs propriétés, y compris des fonctions de minimisation et d'invariance dans des conditions spécifiques.

Couvre les algorithmes d'optimisation, l'appariement stable et la notation Big-O pour l'efficacité de l'algorithme.

Explore le problème de l'arrêt, démontrant son insolvabilité et les limites des algorithmes.