Skip to content

Research at St Andrews

Minimal and canonical images

Research output: Contribution to journalArticle

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
StateE-pub ahead of print - 22 Nov 2018

    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. New refiners for permutation group search

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

    Research output: Contribution to journalArticle

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

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

  4. GAP – Groups, Algorithms, and Programming, Version 4.9.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. 4 Jul 2018

    Research output: Non-textual formSoftware

  5. GAP – Groups, Algorithms, and Programming, Version 4.9.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. 5 May 2018

    Research output: Non-textual formSoftware

Related by journal

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

  2. Enumeration of idempotents in planar diagram monoids

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

    Research output: Contribution to journalArticle

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

  4. Maximal subsemigroups of finite transformation and diagram monoids

    East, J., Kumar, J., Mitchell, J. D. & Wilson, W. A. 15 Jun 2018 In : Journal of Algebra. 504, p. 176-216

    Research output: Contribution to journalArticle

ID: 249277296