Skip to content

Research at St Andrews

Minimal and canonical images

Research output: Contribution to journalArticle

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. 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

  2. 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 journalArticle

  3. 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

  4. GAP – Groups, Algorithms, and Programming, Version 4.10.0

    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., 1 Nov 2018

    Research output: Non-textual formSoftware

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

    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., 5 Sep 2018

    Research output: Non-textual formSoftware

Related by journal

  1. Enumeration of idempotents in planar diagram monoids

    Dolinka, I., East, J., Evangelou, A., FitzGerald, D., Ham, N., Hyde, J., Loughlin, N. & Mitchell, J. D., 15 Mar 2019, In : Journal of Algebra. 522, p. 351-385 35 p.

    Research output: Contribution to journalArticle

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

    Bray, J., Cai, Q., Cameron, P. J., Spiga, P. & Zhang, H., 8 Mar 2019, In : Journal of Algebra. 16 p.

    Research output: Contribution to journalArticle

  3. Computing maximal subsemigroups of a finite semigroup

    Donoven, C. R., Mitchell, J. D. & Wilson, W. A., 1 Jul 2018, In : Journal of Algebra. 505, p. 559-596 38 p.

    Research output: Contribution to journalArticle

  4. Finiteness properties of direct products of algebraic structures

    Mayr, P. & Ruskuc, N., 15 Jan 2018, In : Journal of Algebra. 494, p. 167-187

    Research output: Contribution to journalArticle

ID: 249277296