SAT-Based Techniques for Lexicographically Smallest Finite Models
DOI:
https://doi.org/10.1609/aaai.v38i8.28643Keywords:
CSO: Satisfiability, CSO: Constraint Satisfaction, CSO: Search, SO: Heuristic SearchAbstract
This paper proposes SAT-based techniques to calculate a specific normal form of a given finite mathematical structure (model). The normal form is obtained by permuting the domain elements so that the representation of the structure is lexicographically smallest possible. Such a normal form is of interest to mathematicians as it enables easy cataloging of algebraic structures. In particular, two structures are isomorphic precisely when their normal forms are the same. This form is also natural to inspect as mathematicians have been using it routinely for many decades. We develop a novel approach where a SAT solver is used in a black-box fashion to compute the smallest representative. The approach constructs the representative gradually and searches the space of possible isomorphisms, requiring a small number of variables. However, the approach may lead to a large number of SAT calls and therefore we devise propagation techniques to reduce this number. The paper focuses on finite structures with a single binary operation (encompassing groups, semigroups, etc.). However, the approach is generalizable to arbitrary finite structures. We provide an implementation of the proposed algorithm and evaluate it on a variety of algebraic structures.Downloads
Published
2024-03-24
How to Cite
Janota, M., Chow, C., Araújo, J., Codish, M., & Vojtěchovský, P. (2024). SAT-Based Techniques for Lexicographically Smallest Finite Models. Proceedings of the AAAI Conference on Artificial Intelligence, 38(8), 8048-8056. https://doi.org/10.1609/aaai.v38i8.28643
Issue
Section
AAAI Technical Track on Constraint Satisfaction and Optimization