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

### Chuya Hayashi

Mitsubishi Electric Corporation Asic, Hyogo, Japan

## 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.

## Cite this article

Chuya Hayashi, The Word Problem for Groups with Regular Relations – Improvement of the Knuth-Bendix Algorithm. Publ. Res. Inst. Math. Sci. 28 (1992), no. 6, pp. 913–942

DOI 10.2977/PRIMS/1195167732