Perfect refiners for permutation group backtracking algorithms

Christopher Jefferson, Rebecca Waldecker*, Wilf A. Wilson

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
7 Downloads (Pure)

Abstract

Backtrack search is a fundamental technique for computing with finite permutation groups, which has been formulated in terms of points, ordered partitions, and graphs. We provide a framework for discussing the most common forms of backtrack search in a generic way. We introduce the concept of perfect refiners to better understand and compare the pruning power available in these different settings. We also present a new formulation of backtrack search, which allows the use of graphs with additional vertices, and which is implemented in the software package VOLE. For each setting, we classify the groups and cosets for which there exist perfect refiners. Moreover, we describe perfect refiners for many naturally-occurring examples of stabilisers and transporter sets, including applications to normaliser and subgroup conjugacy problems for 2-closed groups.

Original languageEnglish
Pages (from-to)18-36
Number of pages19
JournalJournal of Symbolic Computation
Volume114
Early online date28 Apr 2022
DOIs
Publication statusPublished - 1 Jan 2023

Keywords

  • Backtrack search
  • Permutation groups
  • Refiners
  • Search algorithms

Fingerprint

Dive into the research topics of 'Perfect refiners for permutation group backtracking algorithms'. Together they form a unique fingerprint.

Cite this