The Word Problem for Groups with Regular Relations – Improvement of the Knuth-Bendix Algorithm

Abstract

The Knuth-Bendix algorithm is a practical algorithm which, for a given finite presentation of a group, finds a finite confluent set of relations, if it terminates. From this confluent set we can know a solution of the word problem for the group. In this paper we introduce a concept of a regular confluent set of relations, which also gives a solution of the word problem, and represent a class of groups with such sets in terms of the Cayley graphs of the groups. Furthermore we make an algorithm to find a regular confluent set of relations as an improvement of the Knuth-Bendix algorithm. This new algorithm is a genuine improvement because there are some finite presentation, for which the Knuth-Bendix algorithm does not stop but the new one does.