Group with solvable word problem: Difference between revisions

Revision as of 00:27, 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
word-hyperbolic 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

@@ Line 13: / Line 13: @@
 ===Stronger properties===
-* [[Weaker than::Finitely generated free group]]
+{| class="sortable" border="1"
-* [[Weaker than::Word-hyperbolic group]]
+! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions
-* [[Weaker than::Group with solvable conjugacy problem]]
+|-
+| [[Weaker than::finitely generated free group]] || || || || {{intermediate notions short|group with solvable word problem|finitely generated free group}}
+|-
+| [[Weaker than::word-hyperbolic group]] || || || || {{intermediate notions short|group with solvable word problem|word-hyperbolic 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 a finite complete rewriting system]] || || || || {{intermediate notions short|group with solvable word problem|group with a finite complete rewriting system}}
+|}
 ===Weaker properties===
-* [[Stronger than::Finitely presented group]]
+{| class="sortable" border="1"
+! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions
+|-
+| [[Stronger than::Finitely presented group]] || || || ||
+|}