Skip to content

Research at St Andrews

Minimal and canonical images

Research output: Contribution to journalArticlepeer-review

Author(s)

Christopher Jefferson, Eliza Jonauskyte, Markus Pfeiffer, Rebecca Waldecker

School/Research organisations

Abstract

We describe a family of new algorithms for finding the canonical image of a set of points under the action of a permutation group. This family of algorithms makes use of the orbit structure of the group, and a chain of subgroups of the group, to efficiently reduce the amount of search that must be performed to find a canonical image.

We present a formal proof of correctness of our algorithms and describe experiments on different permutation groups that compare our algorithms with the previous state of the art.
Close

Details

Original languageEnglish
Pages (from-to)481-506
JournalJournal of Algebra
Volume521
Early online date22 Nov 2018
DOIs
Publication statusPublished - 1 Mar 2019

    Research areas

  • Minimal images, Canonical images, Computation, Group theory, Permutation groups

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Strong external difference families in abelian and non-abelian groups

    Huczynska, S., Jefferson, C. & Nepšinská, S., 8 Feb 2021, In: Cryptography and Communications . First Online, 11 p.

    Research output: Contribution to journalArticlepeer-review

  2. Athanor: high-level local search over abstract constraint specifications in Essence

    Attieh, S., Dang, N., Jefferson, C., Miguel, I. & Nightingale, P., 10 Aug 2019, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19). Kraus, S. (ed.). International Joint Conferences on Artificial Intelligence, p. 1056-1063 8 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  3. GAP – Groups, Algorithms, and Programming, Version 4.10.2

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 19 Jun 2019

    Research output: Non-textual formSoftware

  4. New refiners for permutation group search

    Jefferson, C., Pfeiffer, M. & Waldecker, R., May 2019, In: Journal of Symbolic Computation. 92, p. 70-92 23 p.

    Research output: Contribution to journalArticlepeer-review

  5. GAP – Groups, Algorithms, and Programming, Version 4.10.1

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 23 Feb 2019

    Research output: Non-textual formSoftware

Related by journal

  1. A transversal property for permutation groups motivated by partial transformations

    Araújo, J., Araújo, J. P., Bentz, W., Cameron, P. J. & Spiga, P., 5 Jan 2021, In: Journal of Algebra. 19 p.

    Research output: Contribution to journalArticlepeer-review

  2. Primitive permutation groups and strongly factorizable transformation semigroups

    Araújo, J., Bentz, W. & Cameron, P. J., 1 Jan 2021, In: Journal of Algebra. 565, p. 513-530

    Research output: Contribution to journalArticlepeer-review

  3. Groups generated by derangements

    Bailey, R. A., Cameron, P. J., Giudici, M. & Royle, G. F., 15 Apr 2021, In: Journal of Algebra. 572, p. 245-262

    Research output: Contribution to journalArticlepeer-review

  4. Involution centralisers in finite unitary groups of odd characteristic

    Glasby, S., Praeger, C. & Roney-Dougal, C. M., 1 Mar 2020, In: Journal of Algebra. 545, p. 245-299

    Research output: Contribution to journalArticlepeer-review

  5. The Hall–Paige conjecture, and synchronization for affine and diagonal groups

    Bray, J., Cai, Q., Cameron, P. J., Spiga, P. & Zhang, H., Mar 2020, In: Journal of Algebra. 545, p. 27-42

    Research output: Contribution to journalArticlepeer-review

ID: 249277296

Top