In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group is the algorithmic problem of deciding whether two words in the generators represent the same element. The word problem is a well-known example of an undecidable problem.
For example, given two bijections and on the interval such that and is known, can you prove that the compositions of and can only generate a finite number of other
bijections on without more information about and ?
The functions and are called the generators, and the set of all finite compositions of and and their inverses[clarify]
is the group they generate. In this case, generators generate
a finite group of order 6 isomorphic to the symmetry group of an equilateral triangle, , hence the equality of two arbitrary finite compositions can be decided.
More precisely, if is a finite set of generators for then the word problem is the membership problem for the formal language of all words in and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on to the group . If is another finite generating set for , then the word problem over the generating set is equivalent to the word problem over the generating set . Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group .
The related but different uniform word problem for a class of recursively presented groups is the algorithmic problem of deciding, given as input a presentation for a group in the class and two words in the generators of , whether the words represent the same element of . Some authors require the class to be definable by a recursively enumerable set of presentations.
and 24 Related for: Word problem for groups information
known as combinatorial group theory, the wordproblemfor a finitely generated group G {\displaystyle G} is the algorithmic problem of deciding whether two...
situations Wordproblem (mathematics), a decision problemfor algebraic identities in mathematics and computer science Wordproblemforgroups, the problem of...
common element.[citation needed] The wordproblemforgroups. The conjugacy problem. The group isomorphism problem. Determining whether two finite simplicial...
schools. One of the first problems suspected to be undecidable, in the second sense of the term, was the wordproblemforgroups, first posed by Max Dehn...
notably the wordproblemforgroups; and the classical Burnside problem. See (Chandler & Magnus 1982) for a detailed history of combinatorial group theory...
relations. The negative solution to the wordproblemforgroups states that there is a finite presentation ⟨S | R⟩ for which there is no algorithm which, given...
unlike the Todd–Coxeter algorithm, it can sometimes solve the wordproblemfor infinite groups. The main practical difficulties in producing a coset enumerator...
finitely presented groups. By the wordproblemforgroups, which is equivalent to the halting problem, it is impossible to classify such groups, so a full topological...
and evolution". List of interstellar and circumstellar molecules Wordproblemforgroups Marshall SM, Mathis C, Carrick E, et al. (24 May 2021). "Identifying...
Novikov is known for his work on combinatorial problems in group theory: the wordproblemforgroups, and his progress in the Burnside problem. In 1955, he...
it homeomorphic to a manifold? The problem is undecidable; the proof is by reduction from the wordproblemforgroups.: 11 Stillwell, John (1993), Classical...
Representation of modular integers by "small" fractions Wordproblemforgroups – Problem in finite group theory O'Connor, John J.; Robertson, Edmund F., "Axel...
problem was formulated by Max Dehn, and together with the wordproblem and conjugacy problem, is one of three fundamental decision problems in group theory...
lemma Partial word Shift space Word metric Wordproblem (computability) Wordproblem (mathematics) Wordproblemforgroups Young–Fibonacci lattice Berstel...
Problem solving is the process of achieving a goal by overcoming obstacles, a frequent part of most activities. Problems in need of solutions range from...
science. Group theory is also central to public key cryptography. Central extension Direct product of groups Direct sum of groups Extension problem Free abelian...
results in number theory Diophantine set Matiyasevich's theorem Wordproblemforgroups Arithmetical hierarchy Subrecursion theory Presburger arithmetic...
Gelfand–Naimark theorem and Naimark's problem Pyotr Novikov, solved the wordproblemforgroups and Burnside's problem Sergei Novikov, worked on algebraic...
Entscheidungsproblem Halting problem Correctness Post correspondence problem Decidable language Undecidable language Wordproblemforgroups Wang tile Penrose tiling...
Year 2000 problem, it made Microsoft Word 5.5 for DOS available for free downloads. As of February 2021[update], it is still available for download from...
1912 Dehn gave an algorithm that solves both the word and conjugacy problemfor the fundamental groups of closed orientable two-dimensional manifolds of...
complete set of these shapes Babai's problem: which groups are Babai invariant groups? Brouwer's conjecture on upper bounds for sums of eigenvalues of Laplacians...
references to nigger have been increasingly replaced by the euphemism "the N-Word", notably in cases where nigger is mentioned but not directly used. In an...
Global Information
![{\displaystyle [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/738f7d23bb2d9642bab520020873cccbef49768d)
