Word problem for groups

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 two-dimensional 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
Bra-ket notation
Groupoid
Cauchy sequence
Forcing (mathematics)
Hash table
Recurrence relation
Pi
Johnston diagram
Principal components analysis
Non-standard analysis
XML
List of trigonometric identities