Computing in permutation and matrix groups. II. Backtrack algorithm
Author:
Gregory Butler
Journal:
Math. Comp. 39 (1982), 671680
MSC:
Primary 2004; Secondary 20E25, 20G40
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.
 [1]
Gregory Butler, Computational Approaches to Certain Problems in the Theory of Finite Groups, Ph. D. Thesis, University of Sydney, 1979.
 [2]
Gregory
Butler, Computing normalizers in permutation groups, J.
Algorithms 4 (1983), no. 2, 163–175. MR 699212
(84j:20003), http://dx.doi.org/10.1016/01966774(83)900433
 [3]
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
(83k:20004a), http://dx.doi.org/10.1090/S00255718198206696583
 [4]
Gregory Butler & John J. Cannon, "Computing in permutation and matrix groups. III: Sylow subgroups." (Manuscript.)
 [5]
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
(82i:20003)
 [6]
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.
 [7]
Christoph M. Hoffman, "On the complexity of intersecting permutation groups and its relationship with graph isomorphism." (Manuscript.)
 [8]
James
F. Hurley and Arunas
Rudvalis, Finite simple groups, Amer. Math. Monthly
84 (1977), no. 9, 693–714. MR 0466269
(57 #6149)
 [9]
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
(81f:05033), http://dx.doi.org/10.1016/00973165(79)900189
 [10]
Jeffrey S. Leon, personal communication.
 [11]
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
(81b:05003)
 [12]
Heinrich Robertz, Eine Methode zur Berechnung der Automorphismengruppe einer endliche Gruppe, Diplomarbeit, R. W. T. H. Aachen, 1976.
 [13]
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
(49 #2901)
 [14]
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.
 [1]
 Gregory Butler, Computational Approaches to Certain Problems in the Theory of Finite Groups, Ph. D. Thesis, University of Sydney, 1979.
 [2]
 Gregory Butler, "Computing normalizers in permutation groups," J. Algorithms. (To appear.) MR 699212 (84j:20003)
 [3]
 Gregory Butler & John J. Cannon, "Computing in permutation and matrix groups. I: Normal closure, commutator subgroup, series," Math. Comp., v. 39, 1982, pp. MR 669658 (83k:20004a)
 [4]
 Gregory Butler & John J. Cannon, "Computing in permutation and matrix groups. III: Sylow subgroups." (Manuscript.)
 [5]
 John J. Cannon, "Software tools for group theory," Proc. Sympos. Pure Math., vol. 37, Amer. Math. Soc., Providence, R. I., 1980, pp. 495502. MR 604627 (82i:20003)
 [6]
 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.
 [7]
 Christoph M. Hoffman, "On the complexity of intersecting permutation groups and its relationship with graph isomorphism." (Manuscript.)
 [8]
 James F. Hurley & Arunas Rudvalis, "Finite simple groups," Amer. Math. Monthly, v. 84, 1977, pp. 693714. MR 0466269 (57:6149)
 [9]
 Jeffrey S. Leon, "An algorithm for computing the automorphism group of a Hadamard matrix," J. Combin. Theory Ser. A, v. 27, 1979, pp. 289306. MR 555799 (81f:05033)
 [10]
 Jeffrey S. Leon, personal communication.
 [11]
 Brendan D. McKay, "Computing automorphisms and canonical labelling of graphs," Lecture Notes in Math., vol. 686, SpringerVerlag, Berlin and New York, 1978, pp. 223232. MR 526749 (81b:05003)
 [12]
 Heinrich Robertz, Eine Methode zur Berechnung der Automorphismengruppe einer endliche Gruppe, Diplomarbeit, R. W. T. H. Aachen, 1976.
 [13]
 Charles C. Sims, "Determining the conjugacy classes of a permutation group," Computers in Algebra and Number Theory (Proc. Sympos. on Appl. Math., New York, 1970), G. Birkhoff and M. Hall, Jr. (eds.), SIAMAMS Proceedings, vol. 4, Amer. Math. Soc., Providence, R. I., 1971. MR 0338135 (49:2901)
 [14]
 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.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
2004,
20E25,
20G40
Retrieve articles in all journals
with MSC:
2004,
20E25,
20G40
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198206696595
PII:
S 00255718(1982)06696595
Keywords:
Backtrack algorithm,
permutation group,
matrix group
Article copyright:
© Copyright 1982 American Mathematical Society
