VI - Applications of Diagrams to Decision Problems

Summary

In this chapter, classical decision problems such as the word and conjugacy problem are introduced and methods are given for solving them in certain cases. All the methods we present involve Van-Kampen diagrams as one of the most powerful tools when dealing with the classical decision problems.

Introduction

In 1912, Max Dehn formulated in his article “Über unendliche diskontinuierliche Gruppen” (“On infinite discontinuous groups”) three fundamental problems for infinite groups given by finite presentations: the identity problem, the transformation problem, and the isomorphism problem. The following is a translation of Dehn's definition of the first two problems called in modern terms the word problem and the conjugacy problem:

1. The identity problem (word problem): Let an arbitrary element of the group be given as a product of the generators. Find a method to decide in a finite number of steps whether or not this element equals the identity element.

2. The transformation problem (conjugacy problem): Any two elements S and T of the group are given as a product of the generators. Find a method to decide whether or not S and T are conjugate, i.e., whether or not there exists an element U of the group that satisfies the equation S = UTU^-1.

In this chapter we wish to give an account of some recent developments that use Dehn's original geometric ideas in extending partial solutions of the word and conjugacy problems, in particular some recent generalizations of smallcancellation theory.