Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

Implementation and analysis of the Todd-Coxeter algorithm


Authors: John J. Cannon, Lucien A. Dimino, George Havas and Jane M. Watson
Journal: Math. Comp. 27 (1973), 463-490
MSC: Primary 20-04
MathSciNet review: 0335610
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A recent form of the Todd-Coxeter algorithm, known as the lookahead algorithm, is described. The time and space requirements for this algorithm are shown experimentally to be usually either equivalent or superior to the Felsch and Haselgrove-Leech-Trotter algorithms. Some findings from an experimental study of the behaviour of Todd-Coxeter programs in a variety of situations are given.


References [Enhancements On Off] (What's this?)

  • [1] M. J. Beetham, A set of generators and relations for the group 𝑃𝑆𝐿(2,𝑞),𝑞 odd, J. London Math. Soc. (2) 3 (1971), 554–557. MR 0285588
  • [2] A. Brunner, Personal communication.
  • [3] C. M. Campbell, Some examples using coset enumeration, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 37–41. MR 0254131
  • [4] H. S. M. Coxeter, "The abstract groups $ {R^m} = {S^m} = {({R^j}{S^j})^{{p_j}}} = 1,{S^m} = {T^2} = {({S^j}T)^{2pj}} = 1$ and $ {S^m} = {T^2} = {({S^{ - j}}T{S^j}T)^{{p_j}}} = 1$," Proc. London Math. Soc. (2), v. 41, 1936, pp. 278-301.
  • [5] H. S. M. Coxeter, The abstract groups 𝐺^{𝑚,𝑛,𝑝}, Trans. Amer. Math. Soc. 45 (1939), no. 1, 73–150. MR 1501984, 10.1090/S0002-9947-1939-1501984-9
  • [6a,b] H. S. M. Coxeter and W. O. J. Moser, Generators and relations for discrete groups, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957. MR 0088489
  • [7] L. A. Dimino, "A graphical approach to coset enumeration," SIGSAM Bulletin, v. 19, 1971, pp. 8-43.
  • [8] H. Felsch, Programmierung der Restklassenabzählung einer Gruppe nach Untergruppen, Numer. Math. 3 (1961), 250–256 (German). MR 0134435
  • [9] M. J. T. Guy, Coset Enumeration, Lecture delivered at the Conference on Computational Problems in Abstract Algebra, Oxford, 29 August-2 September, 1967.
  • [10] Graham Higman and John McKay, On Janko’s simple group of order 50,232,960, Bull. London Math. Soc. 1 (1969), 89–94; correction, ibid. 1 (1969), 219. MR 0246955
  • [11] John Leech, Coset enumeration on digital computers, Proc. Cambridge Philos. Soc. 59 (1963), 257–267. MR 0146994
  • [12] John Leech, Generators for certain normal subgroups of (2,3,7), Proc. Cambridge Philos. Soc. 61 (1965), 321–332. MR 0174621
  • [13] John Leech, Coset enumeration, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 21–35. MR 0254133
  • [14] John Leech, Note on a conjecture of Coxeter, Proc. Glasgow Math. Assoc. 5 (1960), 25–29 (1961) (French). MR 0150193
  • [15] I. D. Macdonald, On a class of finitely presented groups, Canad. J. Math. 14 (1962), 602–613. MR 0140574
  • [16] John McKay and David Wales, The multipliers of the simple groups of order 604,800 and 50,232,960, J. Algebra 17 (1971), 262–272. MR 0274577
  • [17] N. S. Mendelsohn, An algorithmic solution for a word problem in group theory, Canad. J. Math. 16 (1964), 509–516. MR 0163949
  • [18] Dietmar Garbe and Jens L. Mennicke, Some remarks on the Mathieu groups, Canad. Math. Bull. 7 (1964), 201–212. MR 0162846
  • [19] B. H. Neumann, Personal communication.
  • [20] J. A. Todd & H. S. M. Coxeter, "A practical method for enumerating cosets of a finite abstract group," Proc. Edinburgh Math. Soc., v. 5, 1936, pp. 26-34.
  • [21] H. F. Trotter, A machine program for coset enumeration, Canad. Math. Bull. 7 (1964), 357–368. MR 0168151
  • [22] J. M. Watson, An Extended Todd-Coxeter Algorithm, Department of Mathematics, Institute of Advanced Studies, Australian National University, Canberra, 1971, 15 pages.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 20-04

Retrieve articles in all journals with MSC: 20-04


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1973-0335610-5
Keywords: Todd-Coxeter algorithm, generators and relations, group theory
Article copyright: © Copyright 1973 American Mathematical Society