Skip to content

Research at St Andrews

Minimal and canonical images

Research output: Contribution to journalArticle

Open Access Status

  • Embargoed (until 22/11/19)

Links

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
JournalJournal of Algebra
VolumeIn press
Early online date22 Nov 2018
DOIs
StateE-pub ahead of print - 22 Nov 2018

    Research areas

  • Minimal images, Canonical images, Computation, Group

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. Complexity of n-Queens completion (extended abstract)

    Gent, I. P., Jefferson, C. A. & Nightingale, P. W. 13 Jul 2018 Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 5608-5611 4 p.

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

  3. A framework for constraint based local search using ESSENCE

    Akgun, O., Attieh, S. W. A., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W., Salamon, A. Z., Spracklen, P. & Wetter, J. P. 13 Jul 2018 Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 1242-1248 7 p.

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

  4. Two variants of the froidure-pin algorithm for finite semigroups

    Jonusas, J., Mitchell, J. D. & Pfeiffer, M. 8 Feb 2018 In : Portugaliae Mathematica. 74, 3, p. 173-200 28 p.

    Research output: Contribution to journalArticle

  5. Automatic discovery and exploitation of promising subproblems for tabulation

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W. & Salamon, A. Z. 2018 Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 11008)

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

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

    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