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

• Finitely generated free group
• Word-hyperbolic group
• Group with solvable conjugacy problem

Weaker properties

• Finitely presented group