Perfect refiners for permutation group backtracking algorithms. (January 2023)

• Record Type: Journal Article
• Authors: Jefferson, Christopher; Waldecker, Rebecca; Wilson, Wilf A.
• Is Part Of: Journal of symbolic computation. Volume 114(2023)
• Page Start: 18
• Page End: 36
• Publication Date: 2023-01
• Subjects: Permutation groups -- Backtrack search -- Search algorithms -- Refiners; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2022.04.007
• Languages: English
• ISSNs: 0747-7171

Abstract

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.