Word Problem For Groups
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element. More precisely, if A is a finite set of generators for G then the word problem is the membership problem for the formal language of all words in A and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on A to the group G. If B is another finite generating set for G, then the word problem over the generating set B is equivalent to the word problem over the generating set A. Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group G.
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.
Read more about Word Problem For Groups: History, A More Concrete Description, Examples, Partial Solution of The Word Problem, Unsolvability of The Uniform Word Problem, Algebraic Structure and The Word Problem
Famous quotes containing the words word, problem and/or groups:
“Every word wants to be taken literally, else it decays into a lie. But one mustn’t take any word literally, else the world becomes a madhouse.”
—Robert Musil (1880–1942)
“Will women find themselves in the same position they have always been? Or do we see liberation as solving the conditions of women in our society?... If we continue to shy away from this problem we will not be able to solve it after independence. But if we can say that our first priority is the emancipation of women, we will become free as members of an oppressed community.”
—Ruth Mompati (b. 1925)
“In America every woman has her set of girl-friends; some are cousins, the rest are gained at school. These form a permanent committee who sit on each other’s affairs, who “come out” together, marry and divorce together, and who end as those groups of bustling, heartless well-informed club-women who govern society. Against them the Couple of Ehepaar is helpless and Man in their eyes but a biological interlude.”
—Cyril Connolly (1903–1974)