Group with solvable word problem
This term is related to: combinatorial group theory
View other terms related to combinatorial group theory | View facts related to combinatorial group theory
This term is related to: geometric group theory
View other terms related to geometric group theory | View facts related to geometric 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.
Relation with other properties
Stronger properties
| Property | Meaning | Proof of implication | Proof of strictness (reverse implication failure) | Intermediate notions |
|---|---|---|---|---|
| finitely generated free group | |FULL LIST, MORE INFO | |||
| finitely generated abelian group | |FULL LIST, MORE INFO | |||
| finitely generated nilpotent group | |FULL LIST, MORE INFO | |||
| polycyclic group | |FULL LIST, MORE INFO | |||
| word-hyperbolic group | |FULL LIST, MORE INFO | |||
| automatic group | Template:Intermediate notion short | |||
| biautomatic group | |FULL LIST, MORE INFO | |||
| group with solvable conjugacy problem | |FULL LIST, MORE INFO | |||
| group with a finite complete rewriting system | |FULL LIST, MORE INFO |
Weaker properties
| Property | Meaning | Proof of implication | Proof of strictness (reverse implication failure) | Intermediate notions |
|---|---|---|---|---|
| Finitely presented group |