| dbo:abstract
|
- Le problème du mot est un problème de décision en algèbre abstraite. Il consiste, pour une présentation donnée d'une structure algébrique, à répondre algorithmiquement (à décider) à la question suivante : étant donnée une paire de termes et de la structure, est-ce que l'égalité est satisfaite ? Le premier problème de mot dont on a démontré l'indécidabilité fut le problème du mot dans les groupes. La démonstration a été annoncé par Tarski en 1949 et publié dans le livre Undecidable Theories. Le problème du mot en logique combinatoire est indécidable. Le problème du mot pour les groupes est indécidable en général, mais décidable dans de nombreux cas : il existe un algorithme qui décide si est vraie dans tous les groupes. Le problème du mot dans les groupes est aussi décidable pour de nombreuses classes de présentations de groupes, par exemple pour les groupes de Coxeter et plus généralement pour les groupes automatiques, mais est indécidable en général, pour une présentation quelconque d'un groupe par générateurs et relations. En 1955, Novikov a même prouvé qu'il existe des présentations de groupes ayant un problème du mot indécidable. De nombreux problèmes de décision en mathématiques peuvent être formulés comme des problèmes du mot (voir la (en)). (fr)
- In computational mathematics, a word problem is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities. A prototypical example is the word problem for groups, but there are many other instances as well. A deep result of computational theory is that answering this question is in many important cases undecidable. (en)
- Na matemática e na ciência da computação, um problema de palavra para um conjunto de S em relação às codificações finitas de seus elementos é o problema algorítmico de decidir se duas representações podem ser usadas para representar o mesmo elemento do conjunto. O problema é geralmente encontrado em álgebra abstrata, onde dada uma representação de uma estrutura algébrica por geradores e relatores, o problema é determinar se duas expressões representam o mesmo elemento; um exemplo seria o problema de palavras para grupos. Informalmente dizendo, o problema de palavras em álgebra é: dado um conjunto de identidades E com duas expressões x e y, será possível transformar x em y utilizando as identidades em E usando as regras de reescrita em ambas as direções ? Embora responder a essa pergunta possa não parecer difícil, o resultado notável (e profundo) que aparece, em vários casos importantes é que o problema é indecidível.Muitos dos problemas indecidíveis na matemática, senão todos podem ser propostos como problemas de palavra; veja a lista de problemas indecidíveis para mais exemplos. (pt)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 29027 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:event
|
- Graham Higman characterises the subgroups of finitely presented groups with Higman's embedding theorem, connecting recursion theory with group theory in an unexpected way and giving a very different proof of the unsolvability of the word problem. (en)
- Alan Turing shows the word problem for cancellation semigroups is unsolvable, by furthering Post’s construction. The proof is difficult to follow but marks a turning point in the word problem for groups. (en)
- Britton presents a greatly simplified version of Boone's 1959 proof that the word problem for groups is unsolvable. It uses a group-theoretic approach, in particular Britton's Lemma. This proof has been used in a graduate course, although more modern and condensed proofs exist. (en)
- William Boone independently shows the word problem for groups is unsolvable, using Post's semigroup construction. (en)
- Axel Thue poses a general problem of term rewriting on tree-like structures. He states "A solution of this problem in the most general case may perhaps be connected with unsurmountable difficulties". (en)
- The Church-Turing thesis emerges, defining formal notions of computability and undecidability. (en)
- Dehn presents Dehn's algorithm, and proves it solves the word problem for the fundamental groups of closed orientable two-dimensional manifolds of genus greater than or equal to 2. Subsequent authors have greatly extended it to a wide range of group theoretic decision problems. (en)
- Emil Post and Andrey Markov Jr. independently construct finitely presented semigroups with unsolvable word problem. Post's construction is built on Turing machines while Markov's uses Post's normal systems. (en)
- Gennady Makanin proves that the existential theory of equations over free monoids is solvable. (en)
- Max Dehn poses the word problem for finitely presented groups. (en)
- Axel Thue poses the word problem for finitely presented semigroups. (en)
- Pyotr Novikov gives the first published proof that the word problem for groups is unsolvable, using Turing’s cancellation semigroup result. The proof contains a "Principal Lemma" equivalent to Britton's Lemma. (en)
- Boone publishes a simplified version of his construction. (en)
- John Britton gives another proof that the word problem for groups is unsolvable, based on Turing's cancellation semigroups result and some of Britton's earlier work. An early version of Britton's Lemma appears. (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In computational mathematics, a word problem is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities. A prototypical example is the word problem for groups, but there are many other instances as well. A deep result of computational theory is that answering this question is in many important cases undecidable. (en)
- Le problème du mot est un problème de décision en algèbre abstraite. Il consiste, pour une présentation donnée d'une structure algébrique, à répondre algorithmiquement (à décider) à la question suivante : étant donnée une paire de termes et de la structure, est-ce que l'égalité est satisfaite ? Le premier problème de mot dont on a démontré l'indécidabilité fut le problème du mot dans les groupes. La démonstration a été annoncé par Tarski en 1949 et publié dans le livre Undecidable Theories. (fr)
- Na matemática e na ciência da computação, um problema de palavra para um conjunto de S em relação às codificações finitas de seus elementos é o problema algorítmico de decidir se duas representações podem ser usadas para representar o mesmo elemento do conjunto. O problema é geralmente encontrado em álgebra abstrata, onde dada uma representação de uma estrutura algébrica por geradores e relatores, o problema é determinar se duas expressões representam o mesmo elemento; um exemplo seria o problema de palavras para grupos. Informalmente dizendo, o problema de palavras em álgebra é: dado um conjunto de identidades E com duas expressões x e y, será possível transformar x em y utilizando as identidades em E usando as regras de reescrita em ambas as direções ? Embora responder a essa pergunta po (pt)
|
| rdfs:label
|
- Problème du mot (fr)
- Problema da palavra (pt)
- Word problem (mathematics) (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
