| Word Problem For Groups |
Article Index for Word Problem |
Website Links For Word |
Information AboutWord Problem For Groups |
| CATEGORIES ABOUT WORD PROBLEM FOR GROUPS | |
| group theory | |
|
The related but different uniform word problem for finitely presented groups is the algorithmic problem of deciding, given as input a Presentation for a group and two words in the generators, whether the words represent the same element in the group defined by the presentation. HISTORY The study of the word problem was first proposed by Max Dehn in 1911 . It was shown by Pyotr Sergeyevich Novikov in 1955 that there exists a finitely generated (in fact, a finitely presented) group ''G'' such that the word problem is for ''G'' is Undecidable . It follows immediately that the uniform word problem is also undecidable. A much simpler proof was obtained by Boone in 1959. The word problem was one of the first examples of an unsolvable problem to be found not in Mathematical Logic or the Theory Of Algorithms , but in one of the central branches of classical mathematics, Algebra . As a result of its unsolvability, several other problems in combinatorial group theory have been shown to be unsolvable as well. It is important to realize that the word problem is in fact solvable for many groups ''G''. For example, see Todd-Coxeter Algorithm and Knuth-Bendix Completion Algorithm . A MORE CONCRETE DESCRIPTION In more concrete terms, the uniform word problem can be expressed as a Rewriting question, for Literal String s. For a presentation ''P'' of a group ''G'', ''P'' will specify a certain number of generators x for ''G''. We need to introduce one letter for ''x'' and another (for convenience) for the group element represented by ''x''−1. Call these letters (twice as many as the generators) the alphabet ''A'' for our problem. Then each element in ''G'' is represented in ''some way'' by a product abc ... pqr of symbols from ''A'', of some length, multiplied in ''G''. The effect of the ''relations'' in ''G'' is to make various such strings represent the same element of ''G''. In fact the relations provide a list of strings that can be either introduced where we want, or cancelled out whenever we see them, without changing the 'value', i.e. the group element that is the result of the multiplication. |
|
|