Group with solvable word problem: Difference between revisions
No edit summary |
|||
| Line 4: | Line 4: | ||
===Symbol-free definition=== | ===Symbol-free definition=== | ||
A '''group with solvable word problem''' is a [[finitely presented group]] with a finite presentation having the following property: given any word in the generators, | A '''group with solvable word problem''' is a [[finitely presented group]] with a finite presentation having the following property: there is an algorithm that, given any word in the generators, can, in finite time, test whether or not that word equals the identity element of the group. | ||
Note that the finite time that the algorithm takes to terminate depends on the word itself. However, since the generating set is finite, there are only finitely many words of a given length, and we can hence obtain a bound on the time the algorithm takes, that depends only on the length of the word. | Note that the finite time that the algorithm takes to terminate depends on the word itself. However, since the generating set is finite, there are only finitely many words of a given length, and we can hence obtain a bound on the time the algorithm takes, that depends only on the length of the word. | ||
Revision as of 13:38, 29 May 2008
This term is related to: combinatorial group theory
View other terms related to combinatorial group theory | View facts related to combinatorial group theory
Definition
Symbol-free definition
A group with solvable word problem is a finitely presented group with a finite presentation having the following property: there is an algorithm that, given any word in the generators, can, in finite time, test whether or not that word equals the identity element of the group.
Note that the finite time that the algorithm takes to terminate depends on the word itself. However, since the generating set is finite, there are only finitely many words of a given length, and we can hence obtain a bound on the time the algorithm takes, that depends only on the length of the word.