Group with solvable word problem: Difference between revisions
| Line 17: | Line 17: | ||
|- | |- | ||
| [[Weaker than::finitely generated free group]] || || || || {{intermediate notions short|group with solvable word problem|finitely generated free group}} | | [[Weaker than::finitely generated free group]] || || || || {{intermediate notions short|group with solvable word problem|finitely generated free group}} | ||
|- | |||
| [[Weaker than::finitely generated abelian group]] || || || || {{intermediate notions short|group with solvable word problem|finitely generated abelian group}} | |||
|- | |||
| [[Weaker than::finitely generated nilpotent group]] || || || || {{intermediate notions short|group with solvable word problem|finitely generated nilpotent group}} | |||
|- | |||
| [[Weaker than::polycyclic group]] || || || || {{intermediate notions short|group with solvable word problem|polycyclic group}} | |||
|- | |- | ||
| [[Weaker than::word-hyperbolic group]] || || || || {{intermediate notions short|group with solvable word problem|word-hyperbolic group}} | | [[Weaker than::word-hyperbolic group]] || || || || {{intermediate notions short|group with solvable word problem|word-hyperbolic group}} | ||
|- | |||
| [[Weaker than::automatic group]] || || || || {{intermediate notion short|group with solvable word problem|automatic group}} | |||
|- | |||
| [[Weaker than::biautomatic group]] || || || || {{intermediate notions short|group with solvable word problem|biautomatic group}} | |||
|- | |- | ||
| [[Weaker than::group with solvable conjugacy problem]] || || || || {{intermediate notions short|group with solvable word problem|group with solvable conjugacy problem}} | | [[Weaker than::group with solvable conjugacy problem]] || || || || {{intermediate notions short|group with solvable word problem|group with solvable conjugacy problem}} | ||
Revision as of 02:10, 1 February 2012
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 |