Word Problem For Groups

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:

    All that remains to the mother in modern consumer society is the role of scapegoat; psychoanalysis uses huge amounts of money and time to persuade analysands to foist their problems on to the absent mother, who has no opportunity to utter a word in her own defence. Hostility to the mother in our societies is an index of mental health.
    Germaine Greer (b. 1939)

    If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.
    Barbara Coloroso (20th century)

    Instead of seeing society as a collection of clearly defined “interest groups,” society must be reconceptualized as a complex network of groups of interacting individuals whose membership and communication patterns are seldom confined to one such group alone.
    Diana Crane (b. 1933)