The word problem for groups with regular relations. Improvement of the Knuth-Bendix algorithm
type: Item
instance of: scholarly article
title: The word problem for groups with regular relations. Improvement of the Knuth-Bendix algorithm
zbMATH Open document ID: 0806.20028
author: Chuya Hayashi
published in: Publications of the Research Institute for Mathematical Sciences, Kyoto University
publication date: 1995-02-15T00:00:00Z
review text: The Knuth-Bendix algorithm finds, for a given finite group presentation, a finite confluent set of relations, if it terminates. From this confluent set one can find a solution of the word problem for the group. The author introduces a notion of a regular confluent set of relations (where `regular' means `accepted by a finite state automaton') which also gives a solution of the word problem. He represents a class of groups with such sets in terms of the Cayley graph of the groups. For example, it is shown that hyperbolic groups have regular confluent sets of relations. The author gives an algorithm to find a regular confluent set of relations as an improvement of the Knuth-Bendix algorithm. There are some finite presentations for which the Knuth-Bendix algorithm does not stop but the new one does. The author reports that the algorithm is implemented as a computer program and gives some examples to which he applies this program.
reviewed by: Oleg Belegradek
Mathematics Subject Classification ID: 20F05
Mathematics Subject Classification ID: 20-04
Mathematics Subject Classification ID: 20F10
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 597463
zbMATH Keywords: finite group presentation
zbMATH Keywords: confluent set of relations
zbMATH Keywords: word problem
zbMATH Keywords: regular confluent set of relations
zbMATH Keywords: finite state automaton
zbMATH Keywords: Cayley graph
zbMATH Keywords: hyperbolic groups
zbMATH Keywords: algorithm
zbMATH Keywords: Knuth-Bendix algorithm
zbMATH Keywords: finite presentations
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.2977/prims/1195167732
OpenAlex ID: W2010988415
cites work: Optimization of LR(k) parsers
cites work: Q4012141
cites work: Presentations of groups and monoids
cites work: Q3772406
cites work: Q5592246
cites work: Q5541339
cites work: Q4011197
DOI: 10.2977/PRIMS/1195167732
description: scientific article; zbMATH DE number 597463