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.

Property Value
dbo:abstract
  • 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 (en) 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. (fr)
  • 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 (en) 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. (fr)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 11283295 (xsd:integer)
dbo:wikiPageLength
  • 17137 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 190610657 (xsd:integer)
dbo:wikiPageWikiLink
prop-fr:année
  • 1911 (xsd:integer)
  • 1912 (xsd:integer)
  • 1955 (xsd:integer)
  • 1958 (xsd:integer)
  • 1966 (xsd:integer)
  • 1969 (xsd:integer)
  • 1972 (xsd:integer)
  • 1973 (xsd:integer)
  • 1974 (xsd:integer)
  • 1982 (xsd:integer)
  • 1986 (xsd:integer)
  • 1990 (xsd:integer)
  • 1991 (xsd:integer)
  • 1994 (xsd:integer)
  • 2001 (xsd:integer)
  • 2018 (xsd:integer)
  • 2021 (xsd:integer)
prop-fr:auteur
prop-fr:collection
  • Classics in Mathematics (fr)
  • Classics in Mathematics (fr)
prop-fr:doi
  • 10.100200 (xsd:double)
  • 10.100700 (xsd:double)
  • 10.101600 (xsd:double)
  • 10.111200 (xsd:double)
prop-fr:fr
  • problème de conjugaison (fr)
  • groupe polycyclique (fr)
  • groupe géométriquement fini (fr)
  • problème de l'isomorphisme de groupes (fr)
  • représentation absolue d'un groupe (fr)
  • résiduellement fini (fr)
  • problème de conjugaison (fr)
  • groupe polycyclique (fr)
  • groupe géométriquement fini (fr)
  • problème de l'isomorphisme de groupes (fr)
  • représentation absolue d'un groupe (fr)
  • résiduellement fini (fr)
prop-fr:isbn
  • 3 (xsd:integer)
  • 978 (xsd:integer)
prop-fr:issn
  • 19 (xsd:integer)
  • 24 (xsd:integer)
  • 25 (xsd:integer)
prop-fr:journal
prop-fr:lang
  • de (fr)
  • en (fr)
  • de (fr)
  • en (fr)
prop-fr:langue
  • en (fr)
  • ru (fr)
  • en (fr)
  • ru (fr)
prop-fr:lieu
  • Berlin, New York (fr)
  • Berlin, New York (fr)
prop-fr:lireEnLigne
prop-fr:mathReviews
  • 260851 (xsd:integer)
  • 263903 (xsd:integer)
  • 314998 (xsd:integer)
  • 840121 (xsd:integer)
  • 1099152 (xsd:integer)
  • 1511645 (xsd:integer)
  • 1511705 (xsd:integer)
prop-fr:nom
  • Collins (fr)
  • Jones (fr)
  • Thomas (fr)
  • Lyndon (fr)
  • Borisov (fr)
  • Schupp (fr)
  • Collins (fr)
  • Jones (fr)
  • Thomas (fr)
  • Lyndon (fr)
  • Borisov (fr)
  • Schupp (fr)
prop-fr:numéro
  • 1 (xsd:integer)
  • 2 (xsd:integer)
  • 3 (xsd:integer)
  • 10 (xsd:integer)
  • 20 (xsd:integer)
prop-fr:pages
  • 1 (xsd:integer)
  • 2 (xsd:integer)
  • 33 (xsd:integer)
  • 41 (xsd:integer)
  • 116 (xsd:integer)
  • 145 (xsd:integer)
  • 185 (xsd:integer)
  • 230 (xsd:integer)
  • 297 (xsd:integer)
  • 305 (xsd:integer)
  • 413 (xsd:integer)
  • 521 (xsd:integer)
  • 1061 (xsd:integer)
prop-fr:pagesTotales
  • 517 (xsd:integer)
  • xiv+339 (fr)
prop-fr:passage
  • 1 (xsd:integer)
prop-fr:prénom
  • Richard M. (fr)
  • Paul E. (fr)
  • Roger C. (fr)
  • Donald J. (fr)
  • V. V. (fr)
  • Sam A. M. (fr)
  • Richard M. (fr)
  • Paul E. (fr)
  • Roger C. (fr)
  • Donald J. (fr)
  • V. V. (fr)
  • Sam A. M. (fr)
prop-fr:responsabilité
  • éditeurs (fr)
  • éditeurs (fr)
prop-fr:texte
  • groupes polycycliques (fr)
  • groupes absolument présentés (fr)
  • groupes géométriquement finis (fr)
  • résiduellement finis (fr)
  • groupes polycycliques (fr)
  • groupes absolument présentés (fr)
  • groupes géométriquement finis (fr)
  • résiduellement finis (fr)
prop-fr:titre
  • An Introduction to the Theory of Groups (fr)
  • Combinatorial Group Theory (fr)
  • On a problem of J. H. C. Whitehead and a problem of Alonzo Church (fr)
  • Word problems of groups: Formal languages, characterizations and decidability (fr)
  • Simple examples of groups with unsolvable word problem (fr)
  • Word and conjugacy problems in groups with only a few defining relations (fr)
  • Combinatorial Group Theory and Fundamental Groups (fr)
  • On a group embedding theorem of V. V. Borisov (fr)
  • The word problem (fr)
  • Word Problems: Decision Problem in Group Theory (fr)
  • Word problem (fr)
  • Transformation der Kurven auf zweiseitigen Flächen (fr)
  • Decision problems for groups - survey and reflections (fr)
  • A simple presentation of a group with unsolvable word problem (fr)
  • On the algorithmic unsolvability of the word problem in group theory (fr)
  • Über unendliche diskontinuierliche Gruppen (fr)
  • The word problem and the isomorphism problem for groups (fr)
  • An algebraic characterization of the solvability of the word problem (fr)
  • The word problem for one-relation monoids: a survey (fr)
  • An Introduction to the Theory of Groups (fr)
  • Combinatorial Group Theory (fr)
  • On a problem of J. H. C. Whitehead and a problem of Alonzo Church (fr)
  • Word problems of groups: Formal languages, characterizations and decidability (fr)
  • Simple examples of groups with unsolvable word problem (fr)
  • Word and conjugacy problems in groups with only a few defining relations (fr)
  • Combinatorial Group Theory and Fundamental Groups (fr)
  • On a group embedding theorem of V. V. Borisov (fr)
  • The word problem (fr)
  • Word Problems: Decision Problem in Group Theory (fr)
  • Word problem (fr)
  • Transformation der Kurven auf zweiseitigen Flächen (fr)
  • Decision problems for groups - survey and reflections (fr)
  • A simple presentation of a group with unsolvable word problem (fr)
  • On the algorithmic unsolvability of the word problem in group theory (fr)
  • Über unendliche diskontinuierliche Gruppen (fr)
  • The word problem and the isomorphism problem for groups (fr)
  • An algebraic characterization of the solvability of the word problem (fr)
  • The word problem for one-relation monoids: a survey (fr)
prop-fr:titreOuvrage
  • Algorithms and Classification in Combinatorial Group Theory (fr)
  • Algorithms and Classification in Combinatorial Group Theory (fr)
prop-fr:trad
  • Conjugacy problem (fr)
  • Group isomorphism problem (fr)
  • Polycyclic group (fr)
  • Absolute presentation of a group (fr)
  • Geometrically finite group (fr)
  • Residually finite (fr)
  • polycyclic group (fr)
  • Conjugacy problem (fr)
  • Group isomorphism problem (fr)
  • Polycyclic group (fr)
  • Absolute presentation of a group (fr)
  • Geometrically finite group (fr)
  • Residually finite (fr)
  • polycyclic group (fr)
prop-fr:url
prop-fr:volume
  • 4 (xsd:integer)
  • 6 (xsd:integer)
  • 15 (xsd:integer)
  • 18 (xsd:integer)
  • 19 (xsd:integer)
  • 30 (xsd:integer)
  • 44 (xsd:integer)
  • 71 (xsd:integer)
  • 72 (xsd:integer)
  • 103 (xsd:integer)
  • 750 (xsd:integer)
prop-fr:wikiPageUsesTemplate
prop-fr:zbl
  • 68.013010 (xsd:double)
prop-fr:éditeur
dct:subject
rdfs:comment
  • 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. (fr)
  • 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. (fr)
rdfs:label
  • Problème du mot pour les groupes (fr)
  • Problème du mot pour les groupes (fr)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is oa:hasTarget of
is foaf:primaryTopic of