JournalsprimsVol. 28, No. 6pp. 913–942

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

  • Chuya Hayashi

    Mitsubishi Electric Corporation Asic, Hyogo, Japan
The Word Problem for Groups with Regular Relations – Improvement of the Knuth-Bendix Algorithm cover
Download PDF

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