The word problem for groups with regular relations. Improvement of the Knuth-Bendix algorithm (Q1328892)

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.