No CrossRef data available.
Article contents
Algorithmic Recognition of Group Actions on Orbitals
Published online by Cambridge University Press: 01 February 2010
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.
An algorithm is given tjat recognises (in O(lN2 log N) time, where N is the size of the input and l the depth of a precalculated Schreier tree) when a transitive group, (G, Ω) is the action on one orbit of the action of G on the set Γ(2) of ordered pairs of distinct elements of some G-set Γ (that us, Ωis isomorphic to an orbital of (G,Γ)). This may be adapted to list all essentially different such actions in O(lN4log N)time, where N is the sum of sizes of the input and output. This will be a useful tool for reducing the degree of a permutation group as an aid to further study of the group.
This algorithm is then extended to provide an algorithm that will (in O(lN3 log N) time) recognise when a transiteve group is the action on one orbit of the action of G on the set Γ{2} ofunorderd pairs of distinct elements of some G-set Γ. An algorithm for finding all essentially different such actions is also provided, running in O(lN4logN) time. (again, N is the sum of the input and output sizes.) It is also indicated how these results may be applied to the more general problem of recognising when an intransitive group (G,Ω) is isomorphic to (G, Γ{2}) for some G-set Γ.
All the algorithms are practical; most have been implementd in GAP, and the code is made available with this paper. In some cases the algorithms are considerably more practical than their asymptotic analyses would suggest.
- Type
- Research Article
- Information
- Copyright
- Copyright © London Mathematical Society 1999
References
1.Babai, L., Cooperman, G., Finkelstein, L. and Seress, Á., ‘Nearly linear time algorithms for permutation groups with a small base’, Proceedings 1991 ACM International Symposium on Symbolic and Algebraic Computation (1991) 200–209.CrossRefGoogle Scholar
2.Beals, R., ’Computing blocks of imprimitivity for small-base groups in nearly linear time’, Groups and Computation, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 11 (ed. Finkelstein, L. and Kantor, W. M., Amer. Math. Soc, Providence, RI, 1993) 17–26.CrossRefGoogle Scholar
3.Brown, Cynthia A., Finkelstein, Larry and Purdom, Paul W., ‘A new base change algorithm for permutation group ’, SIAM J. Comput. 18 (1989) 1037–1047.CrossRefGoogle Scholar
4.Butler, Gregory, Fundamental algorithms for permutation groups, Lecture Notes in Computer Science 559 (Springer-Verlag, 1991).CrossRefGoogle Scholar
5.Cooperman, Gene and Finkelstein, Larry, ‘Random algorithms for permutation groups’, CWI Quarterly 5 (1992) 107–125.Google Scholar
6.Schönert, Martin and Seress, Ákos, ‘Finding blocks of imprimitivity in small-base groups in nearly linear time’, Proceedings 1994 ACM-SIGSAM International Symposium on Symbolic and Algebraic Computation (1994) 154–157.Google Scholar
7.Schönert, Martin et al. , GAP — Groups, algorithms and programming (Lehrstuhl D für Mathematik, Rheinisch Westfalische Technische Hochschule, Aachen, Germany, 1994).Google Scholar
8.Sharp, Graham, ‘Algorithmic recognition of actions of 2-homogeneous groups on pairs’, LMSJ. Comput. Math. 1 (1998) 109–147 http://www.lms.ac.uk/jcm/1/lms97008/.Google Scholar
JCM 2 Sharp Appendix A Part 1
Sharp Appendix A Part 1
File
9.7 KB
JCM 2 Sharp Appendix A Part 2
Sharp Appendix A Part 2
File
28 KB
JCM 2 Sharp Appendix A Part 3
Sharp Appendix A Part 3
File
29.4 KB
JCM 2 Sharp Appendix A Part 4
Sharp Appendix A Part 4
File
19 KB
JCM 2 Sharp Appendix A Part 5
Sharp Appendix A Part 5
File
28.9 KB
JCM 2 Sharp Appendix A Part 6
Sharp Appendix A Part 6
File
9.8 KB
You have
Access