This note describes two examples in which the Knuth-Bendix procedure for strings is more useful than coset enumeration for studying a finitely presented group.
Coset enumeration is a procedure for verifying that a subgroup of a finitely presented group has finite index. The procedure was first described in Todd & Coxeter (1936). A survey of coset enumeration and additional references may be found in Neubiiser (1982). The general Knuth-Bendix procedure is described in Knuth & Bendix (1970). A special case, called the Knuth-Bendix procedure for strings, constructs a confluent presentation for a finitely presented monoid, provided such a presentation exists. A version of this procedure for finitely presented groups is discussed in Le Chenadec (1986). This paper assumes a familiarity with both procedures.
If a finitely presented group G is finite, then enumerating the cosets of the trivial subgroup will verify this fact. An alternative method for verifying the finiteness of G is to apply the Knuth-Bendix procedure for strings to the presentation for G. A confluent presentation will be produced and finiteness can be verified using standard techniques from the theory of finite state automata. See Gilman (1979) for details.
Some comparisons have been made of the relative usefulness of coset enumeration and the Knuth-Bendix procedure for strings in situations where both are applicable. Most of these comparisons have favored coset enumeration. Two examples will be described which suggest that in very difficult problems the Knuth-Bendix procedure for strings may be superior to coset enumeration.
The first example concerns a family of presentations due to B. H. Neumann, who suggested that the members of the family would provide a challenge for coset enumeration programs. The first member of the family was given originally in Higman (1951). It is the presentation on generators r, s, t with relations t-lrtr -2= 1, r-~srs -2 = 1, s-~tst -2= 1.