L. Bahai, G. Cooperman, L. Finkelstein, E.M. Luks, and /k. Seress, "Fast Monte Carlo Algorithms for Permutation Groups", $3rd ACM STOG (1991), to app.

Digital Library

Google Scholar

[6]

L. Babai, E. Luks, and/~. Seress, "Fast Management of Permutation Groups", Proc. ~9th IEEE FOCS (1988), pp. 272-282.

Google Scholar

[7]

L. Babai and E. Szemer~di, "On the Complexity of Matrix Group Problems I," Proc. $5th IEEE FOCS (1984), Palm Beach, FL, pp. 229-240.

Google Scholar

[8]

K. Blaha, "The Greedy Algorithm and Bases for Permutation Groups", J. Algorithms, to appear.

Google Scholar

[9]

C.A. Brown, L. Finkelstein, and P.W. Purdom, "A New Base Change Algorithm for Permutation Groups", SIAM J. Computing 18 (1989), pp. 1037-1047.

Digital Library

Google Scholar

[10]

P.J. Cameron, "Finite Permutation Groups and Finite Simple Groups", Bull. London Math. Soc., 13, 1981, pp+ 1-22.

Crossref

Google Scholar

[11]

H. Chernoff, "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations", Ann. Math. Star. 23, (1952), pp. 493-507.

Crossref

Google Scholar

[12]

J.H. Conway et al., Atlas o} Finite Groups, Clarendon Press, Oxford, 1985.

Google Scholar

[13]

G. Cooperman and L. Finkelstein, "A Strong Generating Test and Short Presentations for Permutation Groups", to appear in J. Symbolic Computation.

Digital Library

Google Scholar

[14]

G. Cooperman, L. Finkelstein and N. Sarawagi, "A Random Base Change Algorithm for Permutation Groups+', Proc. Internat. Symp. on Symbolic and A1- gob. Comput., Tokyo, 1990, ACM Press and Addison- Wesley, pp. 161-168.

Digital Library

Google Scholar

[15]

M. Purst, J. Hopcroft and E. Luks, "Polynomial Time Algorithms For Permutation Groups", Proc. ~1st IEEE FOCS (1980), pp. 36-41.

Google Scholar

[16]

M. Hall, Jr., The Theory o} Groups, Macmillan, New York, 1959.

Google Scholar

[17]

M. Jerrum, "A Compact Representation for Permutation Groups", J. Algorithms 7 (1986), pp. 60-78.

Digital Library

Google Scholar

[18]

W.M. Kantor, "Permutation Representations of the Finite Classical Groups of Small Degree or Rank", 2. Algebra 60 (1979), pp. 158-168.

Crossref

Google Scholar

[19]

D.E. Knuth, "Notes on Efficient Representation of Perm Groups" Combinatorica 11 (199t), pp. 57-68 (preliminary version circulated since 1981).

Google Scholar

[20]

C.C. Sims, "Computation with Permutation Groups", in Proc. Second Syrup. on Symbolic and Algeb. Manip., (S.R. Petrick, ed.), ACM, New York, 1971.

Digital Library

Google Scholar

Cited By

View all

Požar R(2023)Fast computation of the centralizer of a permutation group in the symmetric groupJournal of Symbolic Computation10.1016/j.jsc.2023.102287(102287)Online publication date: Dec-2023
https://doi.org/10.1016/j.jsc.2023.102287
Betten AEmiris IZhi LMantzaflaris A(2020)The orbiter ecosystem for combinatorial dataProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3403984(30-37)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.1145/3373207.3403984
Babai L(2011)Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las VegasComputer Science – Theory and Applications10.1007/978-3-642-20712-9_13(162-180)Online publication date: 2011
https://doi.org/10.1007/978-3-642-20712-9_13
Show More Cited By

Index Terms

Nearly linear time algorithms for permutation groups with a small base
1. Computing methodologies
  1. Symbolic and algebraic manipulation
2. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
  2. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods

Recommendations

Permutation tableaux and permutation patterns

In this paper we introduce and study a class of tableaux which we call permutation tableaux; these tableaux are naturally in bijection with permutations, and they are a distinguished subset of the -diagrams of Alex Postnikov [A. Postnikov, Webs in ...
Linear Time Algorithms for Generalizations of the Longest Common Substring Problem

In its simplest form, the longest common substring problem is to find a longest substring common to two or multiple strings. Using (generalized) suffix trees, this problem can be solved in linear time and space. A first generalization is the k -common ...
On the sign-imbalance of permutation tableaux

Permutation tableaux were introduced by Steingrmsson and Williams. Corteel and Kim defined the sign of a permutation tableau in terms of the number of unrestricted columns. The sign-imbalance of permutation tableaux of length n is the sum of signs over ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISSAC '91: Proceedings of the 1991 international symposium on Symbolic and algebraic computation

June 1991

468 pages

ISBN:0897914376

DOI:10.1145/120694

Editor:
Stephen M. Watt

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSAC 91

Sponsor:

German Comp Soc
GMD
SIGSAM

ISSAC 91: International Symposium on Symbolic Algebraic Computation

July 15 - 17, 1991

Bonn, West Germany

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
447
Total Downloads

Downloads (Last 12 months)70
Downloads (Last 6 weeks)14

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Požar R(2023)Fast computation of the centralizer of a permutation group in the symmetric groupJournal of Symbolic Computation10.1016/j.jsc.2023.102287(102287)Online publication date: Dec-2023
https://doi.org/10.1016/j.jsc.2023.102287
Betten AEmiris IZhi LMantzaflaris A(2020)The orbiter ecosystem for combinatorial dataProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3403984(30-37)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.1145/3373207.3403984
Babai L(2011)Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las VegasComputer Science – Theory and Applications10.1007/978-3-642-20712-9_13(162-180)Online publication date: 2011
https://doi.org/10.1007/978-3-642-20712-9_13
Sharp G(2010)Algorithmic Recognition of Actions of 2-Homogeneous Groups on PairsLMS Journal of Computation and Mathematics10.1112/S14611570000001641(109-147)Online publication date: 1-Feb-2010
https://doi.org/10.1112/S1461157000000164
Sharp G(2010)Algorithmic Recognition of Group Actions on OrbitalsLMS Journal of Computation and Mathematics10.1112/S146115700000005X2(1-27)Online publication date: 1-Feb-2010
https://doi.org/10.1112/S146115700000005X
Babai LSzegedy M(2008)Local Expansion of Symmetrical GraphsCombinatorics, Probability and Computing10.1017/S09635483000000311:1(1-11)Online publication date: 12-Sep-2008
https://doi.org/10.1017/S0963548300000031
Robinson ECooperman GTrager B(2006)A parallel architecture for disk-based computing over the Baby Monster and other large finite simple groupsProceedings of the 2006 international symposium on Symbolic and algebraic computation10.1145/1145768.1145817(298-305)Online publication date: 9-Jul-2006
https://dl.acm.org/doi/10.1145/1145768.1145817
Neunhöffer MSeress ÁTrager B(2006)A data structure for a uniform approach to computations with finite groupsProceedings of the 2006 international symposium on Symbolic and algebraic computation10.1145/1145768.1145811(254-261)Online publication date: 9-Jul-2006
https://dl.acm.org/doi/10.1145/1145768.1145811
Cooperman GRobinson EHong H(2003)Memory-based and disk-based algorithms for very high degree permutation groupsProceedings of the 2003 international symposium on Symbolic and algebraic computation10.1145/860854.860877(66-73)Online publication date: 3-Aug-2003
https://dl.acm.org/doi/10.1145/860854.860877
Babai LSaks M(1997)The growth rate of vertex-transitive planar graphsProceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms10.5555/314161.314390(564-573)Online publication date: 5-Jan-1997
https://dl.acm.org/doi/10.5555/314161.314390
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Permutation tableaux and permutation patterns

Linear Time Algorithms for Generalizations of the Longest Common Substring Problem

On the sign-imbalance of permutation tableaux