Computing in permutation and matrix groups. II. Backtrack algorithm
Author:
Gregory Butler
Journal:
Math. Comp. 39 (1982), 671680
MSC:
Primary 2004; Secondary 20E25, 20G40
DOI:
https://doi.org/10.1090/S00255718198206696595
MathSciNet review:
669659
Fulltext PDF Free Access
Abstract  References  Similar Articles  Additional Information
Abstract: This is the second paper in a series which discusses computation in permutation and matrix groups of very large order. The essential aspects of a backtrack algorithm which searches these groups are presented. We then uniformly describe algorithms for computing centralizers, intersections, and set stabilizers, as well as an algorithm which determines whether two elements are conjugate.

Gregory Butler, Computational Approaches to Certain Problems in the Theory of Finite Groups, Ph. D. Thesis, University of Sydney, 1979.
 Gregory Butler, Computing normalizers in permutation groups, J. Algorithms 4 (1983), no. 2, 163–175. MR 699212, DOI https://doi.org/10.1016/01966774%2883%29900433
 Gregory Butler and John J. Cannon, Computing in permutation and matrix groups. I. Normal closure, commutator subgroups, series, Math. Comp. 39 (1982), no. 160, 663–670. MR 669658, DOI https://doi.org/10.1090/S00255718198206696583 Gregory Butler & John J. Cannon, "Computing in permutation and matrix groups. III: Sylow subgroups." (Manuscript.)
 John J. Cannon, Software tools for group theory, The Santa Cruz Conference on Finite Groups (Univ. California, Santa Cruz, Calif., 1979) Proc. Sympos. Pure Math., vol. 37, Amer. Math. Soc., Providence, R.I., 1980, pp. 495–502. MR 604627 John J. Cannon, Robyn Gallagher & Kim McAllister, "STACKHANDLER: A language extension for low level set processing," Programming and Implementation Manual, TR 5, ComputerAided Mathematics Project, Department of Pure Mathematics, University of Sydney, 1974. Christoph M. Hoffman, "On the complexity of intersecting permutation groups and its relationship with graph isomorphism." (Manuscript.)
 James F. Hurley and Arunas Rudvalis, Finite simple groups, Amer. Math. Monthly 84 (1977), no. 9, 693–714. MR 466269, DOI https://doi.org/10.2307/2321249
 Jeffrey S. Leon, An algorithm for computing the automorphism group of a Hadamard matrix, J. Combin. Theory Ser. A 27 (1979), no. 3, 289–306. MR 555799, DOI https://doi.org/10.1016/00973165%2879%29900189 Jeffrey S. Leon, personal communication.
 Brendan D. McKay, Computing automorphisms and canonical labellings of graphs, Combinatorial mathematics (Proc. Internat. Conf. Combinatorial Theory, Australian Nat. Univ., Canberra, 1977) Lecture Notes in Math., vol. 686, Springer, Berlin, 1978, pp. 223–232. MR 526749 Heinrich Robertz, Eine Methode zur Berechnung der Automorphismengruppe einer endliche Gruppe, Diplomarbeit, R. W. T. H. Aachen, 1976.
 Charles C. Sims, Determining the conjugacy classes of a permutation group, Computers in algebra and number theory (Proc. SIAMAMS Sympos. Appl. Math., New York, 1970) Amer. Math. Soc., Providence, R.I., 1971, pp. 191–195. SIAMAMS Proc., Vol. IV. MR 0338135 Charles C. Sims, "Computation with permutation groups," Proc. Second Sympos. on Symbolic and Algebraic Manipulation (Los Angeles, 1971), S. R. Petrick (ed.), A. C. M., New York, 1971.
Retrieve articles in Mathematics of Computation with MSC: 2004, 20E25, 20G40
Retrieve articles in all journals with MSC: 2004, 20E25, 20G40
Additional Information
Keywords:
Backtrack algorithm,
permutation group,
matrix group
Article copyright:
© Copyright 1982
American Mathematical Society