v respectively. Note that an application of a rewrite rule need not reduce the length of a word, and it may indeed lengthen the word.
Collins and Miller (unpublished) have verified that some of the groups constructed in the Boone-Britton proofs of the unsolvability of the word problem have cohomological dimension 2. 12. There exists a finitely presented group G of cohomological dimension 2 having unsolvable word problem. Indeed, G can be obtained from a free group by applying three successive HNN-extensions where the associated subgroups are finitely generated free groups. THEOREM Of course the associated subgroups in the second and third HNN-extension are only free subgroups of the previous stage in the construction, not subgroups of the original free group.
By the Higman embedding theorem, S can be embedded in a finitely presented group H. This completes the proof. Small cancellation groups: A subset R of a free group F is symmetrized if all of the elements of R are cyclically reduced and if r E R implies that all cyclically reduced conjugates of r±l are also in R. Thus the words in R are all cyclically reduced and are closed under taking inverses and cyclic permutations. Let N =< R >F be the normal closure of R in F. Clearly any presentation (respectively, finite presentation) of a group can be converted to a presentation on the same set of generators with a symmetrized set (respectively, finite symmetrized set) of defining relators.
Algorithms and Classification in Combinatorial Group Theory by Charles F. Miller III (auth.), Gilbert Baumslag, Charles F. Miller III (eds.)