Word problem (mathematics)
http://dbpedia.org/resource/Word_problem_(mathematics) an entity of type: Thing
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.
rdf:langString
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.
rdf:langString
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
rdf:langString
rdf:langString
Problème du mot
rdf:langString
Problema da palavra
rdf:langString
Word problem (mathematics)
xsd:integer
3852079
xsd:integer
1113328914
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
William Boone independently shows the word problem for groups is unsolvable, using Post's semigroup construction.
rdf:langString
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".
rdf:langString
The Church-Turing thesis emerges, defining formal notions of computability and undecidability.
rdf:langString
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.
rdf:langString
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.
rdf:langString
Gennady Makanin proves that the existential theory of equations over free monoids is solvable.
rdf:langString
Max Dehn poses the word problem for finitely presented groups.
rdf:langString
Axel Thue poses the word problem for finitely presented semigroups.
rdf:langString
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.
rdf:langString
Boone publishes a simplified version of his construction.
rdf:langString
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.
rdf:langString
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)).
rdf:langString
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.
rdf:langString
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.
xsd:nonNegativeInteger
29027
