Skip to content

Research at St Andrews

New refiners for permutation group search

Research output: Contribution to journalArticlepeer-review

Standard

New refiners for permutation group search. / Jefferson, Christopher; Pfeiffer, Markus; Waldecker, Rebecca.

In: Journal of Symbolic Computation, Vol. 92, 05.2019, p. 70-92.

Research output: Contribution to journalArticlepeer-review

Harvard

Jefferson, C, Pfeiffer, M & Waldecker, R 2019, 'New refiners for permutation group search', Journal of Symbolic Computation, vol. 92, pp. 70-92. https://doi.org/10.1016/j.jsc.2017.12.003

APA

Jefferson, C., Pfeiffer, M., & Waldecker, R. (2019). New refiners for permutation group search. Journal of Symbolic Computation, 92, 70-92. https://doi.org/10.1016/j.jsc.2017.12.003

Vancouver

Jefferson C, Pfeiffer M, Waldecker R. New refiners for permutation group search. Journal of Symbolic Computation. 2019 May;92:70-92. https://doi.org/10.1016/j.jsc.2017.12.003

Author

Jefferson, Christopher ; Pfeiffer, Markus ; Waldecker, Rebecca. / New refiners for permutation group search. In: Journal of Symbolic Computation. 2019 ; Vol. 92. pp. 70-92.

Bibtex - Download

@article{5286402763bf4373b4a17b794318a6ea,
title = "New refiners for permutation group search",
abstract = "Partition backtrack is the current generic state of the art algorithm to search for subgroups of a given permutation group. We describe an improvement of partition backtrack for set stabilizers and intersections of subgroups by using orbital graphs. With extensive experiments we demonstrate that our methods improve performance of partition backtrack – in some cases by several orders of magnitude.",
keywords = "Backtrack search, Refiners, Permutation groups, Algorithmic group theory, Computational algebra, Partition backtrack",
author = "Christopher Jefferson and Markus Pfeiffer and Rebecca Waldecker",
year = "2019",
month = may,
doi = "10.1016/j.jsc.2017.12.003",
language = "English",
volume = "92",
pages = "70--92",
journal = "Journal of Symbolic Computation",
issn = "0747-7171",
publisher = "Academic Press Inc.",

}

RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - New refiners for permutation group search

AU - Jefferson, Christopher

AU - Pfeiffer, Markus

AU - Waldecker, Rebecca

PY - 2019/5

Y1 - 2019/5

N2 - Partition backtrack is the current generic state of the art algorithm to search for subgroups of a given permutation group. We describe an improvement of partition backtrack for set stabilizers and intersections of subgroups by using orbital graphs. With extensive experiments we demonstrate that our methods improve performance of partition backtrack – in some cases by several orders of magnitude.

AB - Partition backtrack is the current generic state of the art algorithm to search for subgroups of a given permutation group. We describe an improvement of partition backtrack for set stabilizers and intersections of subgroups by using orbital graphs. With extensive experiments we demonstrate that our methods improve performance of partition backtrack – in some cases by several orders of magnitude.

KW - Backtrack search

KW - Refiners

KW - Permutation groups

KW - Algorithmic group theory

KW - Computational algebra

KW - Partition backtrack

U2 - 10.1016/j.jsc.2017.12.003

DO - 10.1016/j.jsc.2017.12.003

M3 - Article

VL - 92

SP - 70

EP - 92

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

SN - 0747-7171

ER -

Related by author

  1. GAP – Groups, Algorithms, and Programming, Version 4.11.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., 2 Mar 2021

    Research output: Non-textual formSoftware

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

  3. GAP – Groups, Algorithms, and Programming, Version 4.11.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., 29 Feb 2020

    Research output: Non-textual formSoftware

  4. Software Carpentry: Programming with GAP: Version 3.0

    Konovalov, A., Torpey, M., Jefferson, C. A. & Software Carpentry team, 13 Aug 2019, Zenodo.

    Research output: Other contribution

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

Related by journal

  1. Lifting tropical bitangents

    Len, Y. & Markwig, H., Jan 2020, In: Journal of Symbolic Computation. 96, p. 122-152

    Research output: Contribution to journalArticlepeer-review

  2. Polynomial-time proofs that groups are hyperbolic

    Holt, D., Linton, S., Neunhoeffer, M., Parker, R., Pfeiffer, M. & Roney-Dougal, C. M., May 2021, In: Journal of Symbolic Computation. 104, p. 419-475

    Research output: Contribution to journalArticlepeer-review

  3. Computing finite semigroups

    East, J., Egri-Nagy, A., Mitchell, J. D. & Péresse, Y., May 2019, In: Journal of Symbolic Computation. 92, p. 110-155 46 p.

    Research output: Contribution to journalArticlepeer-review

  4. Integrality and arithmeticity of solvable linear groups

    Detinko, A., Flannery, D. & de Graaf, W., 2015, In: Journal of Symbolic Computation. 68, p. 138–145

    Research output: Contribution to journalArticlepeer-review

ID: 245468143

Top