Some applications of prefix-rewriting in monoids, groups, and rings (Q2702053)

The paper gives a survey on string rewriting techniques that are applicable for the subgroup problem (i.e., generalized word problem), the index problem and the subgroup presentation problem in combinatorial group theory. In general, the mentioned problems are (algorithmically) undecidable for finitely presented groups, but they are decidable for special classes of groups. The paper concentrates on prefix-rewriting, which is well suited for the subgroup and related problems. In this technique the rewriting is performed at the beginning of strings, that is, a string \(\ell u\) is replaced by \(ru\) by a given rewriting rule \(\ell\to r\).NEWLINENEWLINENEWLINEIn particular, the authors show how finitely generated subgroups of certain finitely presented groups can be described by convergent (Noetherian and confluent) prefix-rewriting systems which are obtained by a Knuth-Bendix style completion procedure. Also, it is shown how the computation of Nielsen reduced sets for a finitely generated subgroup of a free group and the Todd-Coxeter coset enumeration can be interpreted as instances of prefix-completion.NEWLINENEWLINEFor the entire collection see [Zbl 0940.00028].