Comparing and combining tools for finitely presented groups

George Havas, Derek F. Holt and Sarah Rees

Abstract

Coset enumeration and the Knuth-Bendix rewriting process are well-established as tools for proving finiteness or otherwise of a finitely presented group. For some situations one is more successful than the other. We compare their performance in proving the finiteness or infiniteness of some challenging examples, and report on some attempts to combine the two tools. We also use the Knuth-Bendix as part of a process in showing some previously problematic groups to be infinite by showing that they are automatic and studying their associated automata.

1 Introduction

Coset enumeration is long established as a technique for the investigation of finitely presented groups. It was used well before the days of electronic computers, apparently first by Moore [17] and subsequently popularized by Todd and Coxeter [22]. The first computer implementation was that of Haselgrove in 1953. This and other early implementations are described in [15].

In its basic usage, coset enumeration takes a finitely presented group together with a finitely generated subgroup as input, and attempts to find the index of that subgroup in the whole group. In principle, it will succeed whenever this index is finite, but in difficult examples it can take a very long time, even when the index is small. If the subgroup can be shown to be finite, then we have a finiteness proof for the whole group. The related Reidemeister-Schreier method can be used to construct a presentation for a finite index subgroup. Then, in suitable circumstances, it is standard to prove infiniteness of the original group through the construction of infinite quotients of such a subgroup. A survey of these and other related techniques can be found in [4].

The use of the Knuth-Bendix process (originally described in [14]) as a tool for group theory was pioneered by Sims. The basic procedure (in its application to groups) is described, for example, in [6] and (in great detail) in [19]. It can be applied to any finite group presentation, and will (in principle) always succeed if the group is finite, and occasionally even when it is infinite. It is also used in combination with other methods in the study of automatic groups, as described in [5]. This can lead to a proof of finiteness or infiniteness in cases when the Knuth-Bendix process alone fails. Such a demonstration is described in [12] of the infiniteness of the Heineken group with presentation

The first author thanks the University of Newcastle and the Australian Research Council for financial support during the period of this research

⟨x, y, z | [x, [x, y]] = z, [y, [y, z]] = x, [z, [z, x]] = y⟩.

The object of this paper is to compare the performance of these two tools as methods of proving finiteness (or occasionally infiniteness). We do this by studying their performance on a number of difficult examples. We also use the idea of combining the two methods, by running Knuth-Bendix for a relatively short time in order to obtain some extra (redundant) relations that hold in the group, and then applying coset enumeration to this larger set of defining relations. We have encountered examples where this combined approach uses the least memory and time overall.

All of the examples we consider here are deficiency zero presentations; that is, presentations with the same number of generators as defining relations. Thus the presentations themselves are relatively concise, suggesting that they may be challenging for computational tools. The first example, in Section 2, is a presentation proposed by Malcolm Wicks, which turns out to be a difficult presentation of the cyclic group of order 11. The second collection of examples, in Section 3, consists of 3-generator and 3-relator presentations devised by Havas, Newman and O’Brien as candidates for deficiency zero presentations of finite p-groups. Most of these have been proved finite; here we show how two of them can be proved infinite, and three remain unresolved. The examples considered in Section 4 are presentations of the groups SL(2, p) due to Campbell and Robertson.

Experience indicates that, as a general rule, coset enumeration is much faster than Knuth-Bendix for straightforward examples. However Sims [20] reports that Knuth-Bendix is able to prove the triviality of the group

G = ⟨ r, s, t | ssr^{−1}s^{−1}rs^{−1}tst^{−1}t^{−1}r^{−1}srs^{−1}s^{−1}tts^{−1}t^{−1}stts^{−1}t^{−1}s
= tts^{−1}t^{−1}st^{−1}rtr^{−1}r^{−1}s^{−1}tst^{−1}t^{−1}rrt^{−1}r^{−1}trrt^{−1}r^{−1}t
= rrt^{−1}r^{−1}tr^{−1}srs^{−1}s^{−1}t^{−1}rtr^{−1}r^{−1}ssr^{−1}s^{−1}rssr^{−1}s^{−1}r = 1 ⟩

which was proposed by B.H. Neumann as a challenge for coset enumeration programs, and which no existing Todd-Coxeter implementation could handle using this presentation as input. The best that latest coset enumeration techniques have achieved is to show that t ∈ ⟨r, s⟩ for G with the presentation above.

It is worth noting that G is constructed by initially considering an easier presentation with relations r^{t}r^{−2} = s^{r}s^{−2} = t^{s}t^{−2} = 1 and iterating it into itself the following way. Let R_{1}, S_{1} and T_{1} be the three relators in this easier presentation. Let R_{2} be the word obtained by substituting R_{1}, S_{1} and T_{1} for r, s and t, respectively, in R_{1}. Likewise let S_{2} and T_{2} be obtained from S_{1} and T_{1} by the same substitution. This yields the above difficult presentation for G which is hard for coset enumeration. However, if we use the six generator presentation

⟨ r, s, t, x, y, z | x = r^{t}r^{−2}, y = s^{r}s^{−2}, z = t^{s}t^{−2}, x^{z}x^{−2} = y^{x}y^{−2} = z^{y}z^{−2} = 1⟩

(which makes the method of construction explicit) coset enumeration handles the group readily enough, even enumerating over the trivial subgroup.

Sims [20] suggests that “in very difficult problems the Knuth-Bendix procedure may be superior to coset enumeration”, and gives further details in [19, pp. 264-265]. Intuitively, this is because Knuth-Bendix is working much harder to deduce and retain all consequences of the currently known relations than coset enumeration, and so one might expect it to take longer but to use less memory; if coset enumeration fails, then it is virtually always a result of running out of space.

Our experiments do provide partial confirmation for this suggestion. At first sight it appears that Knuth-Bendix is superior for the Wicks group and the Campbell-Robertson presentations of SL(2, p), whereas coset enumeration is superior for the Havas-Newman-O’Brien examples. However, first impressions of this kind are potentially misleading in various ways, and the following factors should be borne in mind when attempting to make serious comparisons between coset enumeration and Knuth-Bendix.

When one or other of these methods is used to prove finiteness or infiniteness of a group for the first time, then one could say that it is that method which has been the most successful, even if other methods or parameter settings later turn out to do the job more efficiently. For the Wicks group, it was the combined approach (or Knuth-Bendix) which first succeeded, whereas for the finite Havas-Newman-O’Brien examples it was coset enumeration. For the Campbell-Robertson examples, the result had already been proved theoretically by Campbell and Robertson themselves.

On the other hand, both coset enumeration and Knuth-Bendix have a large number of controlling parameters (see below for further details) that can be set by the user before the run, and which can have huge effects on performance. If we carry out lengthy experiments, trying different values of these parameters, on an example for which we know the answer already, then we may eventually find some particular setting that completes unusually quickly. This does not increase our mathematical knowledge, and it is perhaps a dubious approach to comparing the relative effectiveness of the two methods. However, it can provide the user with experience that may turn out to be useful later on new examples.

The Todd-Coxeter process has the advantage that it can be used most effectively to enumerate the cosets of a nontrivial subgroup of the full group. Although Knuth-Bendix can be run on the cosets of a subgroup, this often does not make it perform any better than it would on the full group. This factor is responsible in part for the superior performance of Todd-Coxeter on the examples that we discuss in Section 3. In many examples, to prove finiteness, it is sufficient if coset enumeration completes over a cyclic subgroup of the given group G, because this tells us that G/K is finite for some cyclic normal subgroup K of G. Since the automorphism group of an infinite cyclic group is finite (of order two), we then know that G/Z(G) is finite, from which it follows by a result of Schur (see Chapter IV, 2.3 of [13]) that the derived group [G, G] of G is also finite. Thus the finiteness of G is equivalent to that of G/[G, G], which can be computed relatively easily. In many of the examples in Section 3, life is even easier, because successful completion of coset enumeration over a 2-generator subgroup enables the theoretical deduction of the order of the group.

The experiments described in this paper were carried out on a number of different computers, which makes precise comparison of cpu-times difficult, but this is not too important in the context of this paper. The coset enumeration implementation used was the one by Havas, based on the description in [8], either as a standalone, or via its interface in the Magma system [1]. It has a wide choice of parameter settings, but the most important are CT and RT, which indicate the relative weightings attached to defining new cosets using the coset table (traditionally called the Felsch strategy) and the relator tables (traditionally known as the HLT strategy). There is a default setting of CT = RT = 0, which is roughly equivalent to HLT + Lookahead.

The Knuth-Bendix packages used were RKBP by Sims (see [21]) and KBMAG by Holt (see [10]). We were not attempting to compare these two packages. Both offer a bewilderingly large choice of parameter settings. The most important is the choice of ordering for words in the generators. The default is the ‘shortlex’ ordering, which means order first by length and then lexicographically using the given generator order, but recursive-path orderings (a special case of ‘wreath product’ orderings; see pages 46–50 of [19]) often produce the best performance for finite groups. It can also be important, particularly with recursive-path orderings, to impose length restrictions on the stored relations, but the most successful numerical restrictions of this kind vary wildly from example to example, and finding them seems to be largely a matter of trial and error.

2 The Wicks Group

Our first example concerns the group

W = ⟨x, y | x^{3}y^{4}x^{5}y^{7} = 1 = x^{2}y^{3}x^{7}y^{8}⟩.

In the Group-pub-forum [7] in 1996, D.L. Johnson reported the failure of coset enumeration to prove W to be cyclic of order 11, leaving a 1987 question of Malcom Wicks unanswered.

Theorem 1 The group ⟨x, y | x^{3}y^{4}x^{5}y^{7} = 1 = x^{2}y^{3}x^{7}y^{8}⟩ is cyclic of order 11.

We believe that W was first proved to be finite by Peter Kenne, who used a combination of Knuth-Bendix and Todd-Coxeter. As far as we know, this was the first use of this technique to solve a previously unsolved problem. For example, one successful strategy was to use Knuth-Bendix to generate 500 new relations in W, and then to use coset enumeration with respect to the subgroup ⟨y⟩ using all of these relations. This completed successfully, with the result |W : ⟨y⟩| = 1, after defining nearly 10 million cosets. From this it follows immediately that G is cyclic, and then we can deduce |G| = 11 by abelianising the presentation. So from the point of view of the first successful solution of an open problem, this represents a success for the combined approach.

However, further experiments by Kenne and others suggest that this particular example is solved much more easily in terms of both time and space by using Knuth-Bendix alone. Using a default shortlex ordering, it completes in about 360 seconds after finding about 26700 relations. Our best result was obtained using a recursive-path ordering with a length limit of 28 on the left and right hand sides of stored equations, when it completed in 162 seconds after finding about 3250 equations. (These timings were on a SparcStation 20.)

In retrospect the Wicks group can be handled by coset enumeration alone. Using principles described by Mendelsohn [16] for the relator table definitions (where cosets are applied to all cyclic permutations of the relators and their inverses) we find that enumeration over ⟨y⟩ gives index 1, defining less than a total of 22 million cosets with CT = 1000, RT = 100. We are grateful to Colin Ramsay for pointing out the perhaps counter-intuitive result that coset enumeration over the smaller subgroup ⟨x⟩ (i.e., in fact the trivial subgroup) is easier. With CT = 10, RT = 100 and Mendelsohn-style definitions we obtain index 11 after defining a total of about 14 million cosets.

3 Some 3-generator examples of deficiency zero

The following fourteen groups are defined by Havas, Newman and O’Brien in [9] as part of a systematic search for finite 3-generator groups of deficiency zero.

#1. ⟨a, b, c | b^{2}c^{−1}bc, a^{2}b^{−1}ab, ca^{−1}b^{−1}cabc⟩,

#2. ⟨a, b, c | b^{2}c^{−1}bc, a^{2}b^{−1}ab, b^{−1}abc^{2}a^{−1}c⟩,

#3. ⟨a, b, c | b^{2}c^{−1}bc, a^{2}b^{−1}ab, ca^{−1}c^{2}b^{−1}ab⟩,

#4. ⟨a, b, c | b^{2}c^{−1}bc, a^{2}b^{−1}ab, cab^{−1}cbca^{−1}⟩,

#5. ⟨a, b, c | b^{2}c^{−1}bc, a^{2}c^{−1}ac, a^{−1}b^{−1}abc^{3}⟩,

#6. ⟨a, b, c | a^{2}c^{−1}ac, bcac^{−1}b^{2}a^{−1}, cbac^{2}b^{−1}a^{−1}⟩,

#7. ⟨a, b, c | a^{2}b^{−1}ab, ab^{2}cba^{−1}c^{−1}, cb^{−1}acbca^{−1}⟩,

#8. ⟨a, b, c | a^{2}c^{−1}ac, acb^{2}a^{−1}c^{−1}b, a^{−1}b^{−1}abc^{3}⟩,

#9. ⟨a, b, c | b^{−1}abca^{2}c^{−1}, acb^{2}c^{−1}a^{−1}b, cb^{−1}acbca^{−1}⟩,

#10. ⟨a, b, c | a^{2}b^{−1}ab, a^{−1}b^{3}c^{−1}ac, a^{−1}bc^{2}ab^{−1}c⟩.

#11. ⟨a, b, c | cac^{−1}b^{−1}aba, bacba^{−1}c^{−1}b, cb^{−1}acbca^{−1}⟩,

#12. ⟨a, b, c | acab^{−1}c^{−1}ab, b^{2}a^{−1}c^{−1}acb, ca^{−1}b^{−1}cabc⟩,

#13. ⟨a, b, c | acab^{−1}c^{−1}ab, acbc^{−1}ba^{−1}b, b^{−1}abc^{2}a^{−1}c⟩,

#14. ⟨a, b, c | a^{3} = [c^{−1}, b], b^{3} = a^{−1}cabc^{−1}b^{−1}, c^{3} = [a^{−1}, b^{−1}][a^{−1}, c][b, c]⟩.

These are all easily shown to have a maximal nilpotent quotient of order 3^{8} by use of the p-quotient program. (In fact, by using his implementation of the Plesken soluble quotient algorithm described in [18], Brückner [2, p. 45] has shown that their maximal soluble quotients all have order 3^{8}.)

Havas, Newman and O’Brien show that the first ten groups indeed have order 3^{8} using coset enumeration. They report that the first five groups yield to coset enumeration over the trivial subgroup, the next four to coset enumeration over a cyclic subgroup, and #10 to coset enumeration over a metacyclic subgroup (plus a theoretical argument). With the availability of improved computer facilities (eg, the SGI Origin 2000 computer at the University of Queensland which allows definition of hundreds of millions of cosets for these examples) the first eight can now all be enumerated over the trivial subgroup, and the next two over cyclic subgroups.

One of our aims was to attempt to find better proofs of finiteness for the first ten groups using Knuth-Bendix, then to go on to attack the remaining four. However, the performance of Knuth-Bendix on these examples was rather disappointing. After trying a wide variety of word-orders and other parameters, with both RKBP and KBMAG, we have only succeeded in obtaining completion in the first eight examples. The hardest of these was #8, where about 27000 equations were found and the computation took about 2600 seconds. The coset enumeration for #8 over the trivial subgroup is likewise hardest and needs to define about 35 million cosets (not readily available in most computing environments) with CT = 1000 and RT = 1. On a comparable machine this takes about 460 seconds.

In Section 1 we reported how using presentations with extra generators helped coset enumeration for G, using a difficult presentation for the trivial group. Since the fourteen groups have largest soluble quotients which are metablian we tried the effect of adding to each presentation three redundant generators defining the commutator subgroup. This gives six generator, six relator presentations which cause coset enumeration and Knuth-Bendix procedures to “think about” the commutator subgroup. This seems a sensible thing to do in the context of the known group structure. Unfortunately these presentations have proved to be more difficult for both coset enumeration and Knuth-Bendix procedures rather than easier.

In part, coset enumeration here can gain a major advantage by enumerating over a nontrivial subgroup. For #9 coset enumeration over ⟨b⟩ yields index 243 with a total of less than half a million cosets and for #10 coset enumeration over ⟨a⟩ yields index 243 with a total of about 16 million cosets (CT = 1000; RT = 1). However coset enumerations over the cyclic subgroups generated by the other given group generators fail to complete after defining more than 300 million cosets. Under these circumstances it is not surprising that Knuth-Bendix procedures do not complete.

Even though this is the case, for #9 we find that the combined approach of running Knuth-Bendix briefly to generate about 1000 additional group relations and adding these to the input of the coset enumeration results in improved performance. The coset enumeration, using the original presentation and the subgroup ⟨b⟩ completes with a maximum of 466982 and total of 473475 cosets, whereas with the additional relations from Knuth-Bendix, it defines only 58281 maximum and 60201 total cosets. (This was with the default setting CT = RT = 0.) Although there is no net gain (and possibly even a slight loss) in cpu-time from using the combined approach, this is still an interesting and significant instance of its usage, because if we had been working with less memory available, then this would have been the only method of solving the problem.

In spite of its lack of success with the two hardest groups which have been proved to be finite in this collection, Knuth-Bendix has an alternative role to play.

Theorem 2 The group ⟨a, b, c | a^{3} = [c^{−1}, b], b^{3} = a^{−1}cabc^{−1}b^{−1}, c^{3} = [a^{−1}, b^{−1}][a^{−1}, c][b, c]⟩ is infinite.

Proof: This is #14. By using the automatic groups program in KBMAG in the same manner as for the proof of infiniteness of F (2, 9) in [11], we succeed in proving that #14 is automatic, and then deducing that it is infinite by consideration of the language of its word-acceptor. (The word-acceptor has 2889 states and each of the multiplier automata has about 8000 states.) □

In the same paper [9], the authors also suggest consideration of the following example, which has maximal nilpotent quotient of order 5^{8}:

⟨a, b, c | a^{2}ca^{3}b^{−1}c^{−1}b, a^{−1}babcb^{3}c^{−1}, cbc^{2}a^{−1}b^{−1}cac⟩.

Theorem 3 The group ⟨a, b, c | a^{2}ca^{3}b^{−1}c^{−1}b, a^{−1}babcb^{3}c^{−1}, cbc^{2}a^{−1}b^{−1}cac⟩ is infinite.

Proof: Again using the automatic groups program in KBMAG, we succeed in deducing that this group is infinite by consideration of the language of its word-acceptor. (The wordacceptor has 1641 states and each of the multiplier automata has about 4000 states.) □

This disposes of one candidate for a 3-generator, 3-relator group of order 5^{8}. There are many others. The following group

⟨a, b, c | a^{2}a^{3bc}, b^{ca^{−1}}b^{4}, c^{ab}c^{4}⟩

passes all of the filters in [9], but we have not yet made any progress towards proving finiteness or infiniteness of this group via either coset enumeration or Knuth-Bendix based techniques. The same is true for groups #11, #12 and #13. (It should be noted that our inability to prove ⟨a, b, c | a^{2}a^{3bc}, b^{ca^{−1}}b^{4}, c^{ab}c^{4}⟩ finite is hardly surprising; no finite p-groups for p > 3 are known which have 3-generator, 3-relator presentations.)

4 Some efficient presentations of SL(2, p)

The following deficiency-zero presentation of G = SL(2, p) for p prime is defined in [3]:

⟨ x, y | x^{2}(xy)^{−3}, (xy^{4}xy^{(p+1)/2})^{2}y^{p}x^{2k} ⟩,

where k is the integral part of p/3. After a modest amount of experimentation with the various parameters, it seems that, as p increases, Knuth-Bendix performs steadily better than coset enumeration when the latter is done over the trivial subgroup.

The table below gives comparative performance figures for Knuth-Bendix and Todd-Coxeter over the identity subgroup. All times are cpu-time in seconds, Knuth-Bendix running on a SparcStation 20 running Solaris 2 and coset enumeration on an SGI Origin 2000 computer. The most successful word-ordering for Knuth-Bendix seemed to be the recursive-path ordering using generator order x < x^{−1} < y < y^{−1}. (Recursive-path ordering is a special case of the wreath product ordering in which each generator and each inverse generator is given a distinct level, with higher levels assigned to higher ordered generator.)

The third column of the table gives the fastest cpu-time (in seconds) achieved. For the larger examples, it proved helpful to impose a maximum length on the words in the stored reduction equations (the same length for both left and right hand sides worked best), and the most successful choice of maximum length is given in the fourth column, while the fifth column gives the maximum number of equations found during the run.

The three final columns describe the Todd-Coxeter performance, listing respectively the cpu-time in successful cases, and the maximum and total numbers of cosets defined. These results are all for the Todd-Coxeter parameters CT = 1000, RT = 1 with the Mendelsohn definition strategy.

Knuth-Bendix  Todd-Coxeter
p |G| time Maxlen Maxeqns time Maxcos  Totcos
3 24  0.03  ∞  22  0.01  425  443
5 120  0.33  ∞  60  0.08  3736  3897
7 336  0.81  ∞  102  0.16  7606  8246
11 1320  14  ∞  711  4.7  200744  206756
13 2184  18  ∞  816  11  379919  397628
17 4896  62  ∞  1712  82  1601126 2050669
19 6840 120  75  2458  256 4731475 6097314
23 12144 960  85  7249  1689 30550041 35792443
29 24360 21153 100  22968 27403 322116445 372387882
31 29760 13672 140  20790 28726 305996059 372986915
37 50616 94987 180  44357  ?

Not surprisingly, Todd-Coxeter performs rather better when enumerating the cosets of one of the subgroups ⟨x⟩ or ⟨y⟩. Since it is easily checked that the group G(p) defined by the presentation is perfect for p ≥ 5, the completion of Todd-Coxeter using a cyclic subgroup is enough to tell us that G(p) is a perfect central extension of SL(2, p) by a cyclic group. We can use the well-known fact that the Schur Multiplier of SL(2, p) is trivial to deduce that G(p) ≅ SL(2, p).

Using the subgroup ⟨y⟩ with the same parameters CT = 1000, RT = 1 and the Mendelsohn definition strategy, Todd-Coxeter completed readily for p ≤ 31. For p = 31, the cpu-time was only 130 seconds, with maximum 1113523 and total 1909300 cosets. This again illustrates the power of coset enumeration when it can be applied over a nontrivial subgroup. For p = 37, coset enumeration succeeded also: the cpu-time was 751 seconds, with maximum 6225117 and total 8112559 cosets.

5 Conclusions

We have compared coset enumeration and Knuth-Bendix rewriting as tools for investigating finitely presented groups. Our examples show that both methods have important roles to play. In some cases where both methods are applicable one shows superior performance to the other in terms of use of computer resources. Furthermore there are situations where answers can be most efficiently obtained using a combination of both tools. We have also showed that some previously problematic groups are infinite by using Knuth-Bendix rewriting as part of the process that shows them to be automatic.

References

[1] W. Bosma, J. Cannon, and C. Playoust. “The Magma algebra system I: the user language”, J. Symbolic Comput. 24 (1997) 235–265.

[2] H. Brückner, “Algorithmen fuer endliche aufloesbare Gruppen und Anwendungen” (Dissertation), Aachener Beitraege zur Mathematik, Band 22, Verlag der Augustinus Buchhandlung (1998).

[3] C.M. Campbell and E.F. Robertson, “A deficiency zero presentation for SL(2, p)”, Bull. Lon. Math. Soc. 12 (1980) 17–20.

[4] J. Cannon and G. Havas, “Algorithms for groups”, Austral. Computer J., 24 (1992) 51–60.

[5] D.B.A. Epstein, D.F. Holt and S.E. Rees, “The use of Knuth-Bendix methods to solve the word problem in automatic groups”, J. of Symbolic Computation 12 (1991) 397–414.

[6] R.H. Gilman, “Presentations of groups and monoids”, J. Algebra 57 (1979) 544-554.

[7] Group-pub-forum e-mail list, group-pub-forum@maths.bath.ac.uk,

http://www2.bath.ac.uk/~masgcs/problem/problem11.html, Problem 11, 1996.

[8] G. Havas, “Coset enumeration strategies”, in Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ACM Press, New York (1991) 191–199.

[9] G. Havas, M.F. Newman and E.A. O’Brien, “Groups of deficiency zero”, in G. Baumslag et al. (eds.), Geometric and Computational Perspectives on Infinite Groups, DI-MACS series in Discrete Mathematics and Theoretical Computer Science 25 (1996) 53–67.

[10] D.F. Holt, KBMAG (Knuth-Bendix in Monoids and Automatic Groups), Software Package, 1992. Available from ftp.warwick.maths.ac.uk in directory

people/dfh/kbmag2.

[11] D.F. Holt, “An alternative proof that the Fibonacci group F (2, 9) is infinite”, Experimental Mathematics 4 (1995) 97–100.

[12] D.F. Holt and D.F. Hurt, “Automatic coset systems and subgroup presentations”, J. Symbolic Computation 27 (1999), 1–20.

[13] B. Huppert, Endliche Gruppen I, Grundlehren Math. Wiss. 134, Springer-Verlag, Berlin, Heidelberg, New York (1967).

[14] D.E. Knuth and P.B. Bendix, “Simple word problems in elementary algebra”, in: (J. Leech, ed.) Computational Problems in Abstract Algebra, Oxford: Pergamon Press (1970) 263–297.

[15] J. Leech, “Coset enumeration on digital computers”, Proc. Camb. Phil. Soc. 59 (1963) 257–267.

[16] N.S. Mendelsohn, “An algorithmic solution for a word problem in group theory”, Canad. J. Math. 16 (1964) 509–516; Correction, Canad. J. Math. 17 (1965) 505.

[17] E.H. Moore, “Concerning the abstract groups of order k! and \frac{1}{2}k! holohedrically isomorphic with the symmetric and alternating substitution-groups on k letters”, Proc. London Math. Soc. (1) 28 (1897) 357–366.

[18] W. Plesken, “Towards a soluble quotient algorithm”, J. Symbolic Computation 4 (1987) 111–122.

[19] C.C. Sims, Computation with finitely presented groups, Encyclopedia of mathematics 48, Cambridge University Press (1994).

[20] C.C. Sims, “The Knuth-Bendix procedure for strings as a substitute for coset enumeration”, J. Symbolic Computation 12 (1991) 439-442.

[21] C.C. Sims, RKBP (The Rutgers Knuth-Bendix Package) Version 1.3, Software Package, 1997.

[22] J.A. Todd and H.S.M. Coxeter, “A practical method for enumerating cosets of finite abstract groups”, Proc. Edinburgh Math. Soc. 5 (1936) 26–34.