Name
Abstract | ||
|---|---|---|
We present new algorithms for permutation group manipulation. Our methods result in an improvement of nearly an order of magnitude in the worst-case analysis for the fundamental problems of finding strong generating sets and testing membership. The normal structure of the group is brought into play even for such elementary issues. An essential element is the recognition of large alternating composition factors of the given group and subsequent extension of the permutation domain to display the natural action of these alternating groups. Further new features include a novel fast handling of alternating groups and the sifting of defining relations in order to link these and other analyzed factors with the rest of the group. The analysis of the algorithm depends on the classification of finite simple groups. In a sequel to this paper, using an enhancement of the present method, we shall achieve a further order of magnitude improvement. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1137/S0097539794229417 | White Plains, NY |
Keywords | Field | DocType |
magnitude improvement,fast management,composition factor,permutation domain,permutation group manipulation,worst-case analysis,present method,permutation groups,strong generating set,new algorithm,finite simple group,new feature,defining relation,permutation group algorithm,permutation group,simple group,alternating group | Discrete mathematics,Combinatorics,Classification of finite simple groups,Permutation,Permutation group,Strong generating set,Bit-reversal permutation,Finite group,Order of magnitude,Mathematics,Base (group theory) | Journal |
Volume | Issue | ISSN |
26 | 5 | 0097-5397 |
ISBN | Citations | PageRank |
0-8186-0877-3 | 26 | 2.89 |
References | Authors | |
20 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laszlo Babai | 1 | 3537 | 573.58 |
| Eugene M. Luks | 2 | 1188 | 299.93 |
| Ákos Seress | 3 | 218 | 36.22 |