
related topics 
{math, number, function} 
{language, word, form} 
{group, member, jewish} 
{specie, animal, plant} 

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a recursively presented group G is the algorithmic problem of deciding whether two words represent the same element. Although it is common to speak of the word problem for the group G strictly speaking it is a presentation of the group that does or does not have solvable word problem. Given two finite presentations P and Q of a group G, P has solvable word problem if and only if Q does.^{[citation needed]} So in this case no confusion is caused by speaking of the word problem for G. When the group is recursively presented but not finitely presented, the distinction becomes important.
The related but different uniform word problem for a class K of recursively presented groups is the algorithmic problem of deciding, given as input a presentation P for a group G in the class K and two words in the generators of G, whether the words represent the same element of G. Some authors require the class K to be definable by a recursively enumerable set of presentations.
Contents
History
Throughout the history of the subject, computations in groups have been carried out using various normal forms. These usually implicitly solve the word problem for the groups in question. In 1911 Max Dehn proposed that the word problem was an important area of study in its own right, (Dehn 1911), together with the conjugacy problem and the group isomorphism problem. In 1912 he gave an algorithm that solves both the word and conjugacy problem for the fundamental groups of closed orientable twodimensional manifolds of genus greater than or equal to 2, (Dehn 1912). Subsequent authors have greatly extended Dehn's algorithm and applied it to a wide range of group theoretic decision problems.^{[1]}^{[2]}^{[3]}
Full article ▸


related documents 
Recursion 
Cantor set 
Finite field 
Inverse function 
Inner product space 
Naive set theory 
Limit superior and limit inferior 
Peano axioms 
Addition 
Matrix multiplication 
Zermeloâ€“Fraenkel set theory 
Computational complexity theory 
Markov chain 
Topological space 
Collatz conjecture 
Pythagorean theorem 
Mathematical induction 
Wavelet 
Braket notation 
Groupoid 
Cauchy sequence 
Forcing (mathematics) 
Hash table 
Recurrence relation 
Pi 
Johnston diagram 
Principal components analysis 
Nonstandard analysis 
XML 
List of trigonometric identities 
