FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Investigating the Existence of Large Sets of Idempotent Quasigroups via Satisfiability Testing

Authors: Pei Huang, Feifei Ma, Jian Zhang, Cunjing Ge and Hantao Zhang

Paper Information

Title:Investigating the Existence of Large Sets of Idempotent Quasigroups via Satisfiability Testing
Authors:Pei Huang, Feifei Ma, Jian Zhang, Cunjing Ge and Hantao Zhang
Proceedings:IJCAR Proceedings 9th IJCAR, 2018
Editors: Stephan Schulz, Didier Galmiche and Roberto Sebastiani
Keywords:SAT, Symmetry breaking, Finite model generator, Idempotent quasigroups, Large set
Abstract:

ABSTRACT. In this paper, we describe a method for solving some open problems in design theory based on SAT solvers. Modern SAT solvers are efficient and can produce unsatisfiability proofs. However, the state-of-the-art SAT solvers cannot solve so-called large set of idempotent quasigroups. Two idempotent quasigroups over the same set of elements are said to be disjoint if at any position other than the main diagonal, the two elements from the two idempotent quasigroups at the same position cannot be the same. A collection of $n-2$ idempotent quasigroups of size n is called a large set if all idempotent quasigroups are mutually disjoint, denoted by LIQ(n). The existence of LIQ(n) satisfying certain identities has been a challenge for modern SAT solvers even if n = 9. We will use a finite model generator to help the SAT solver avoiding symmetric search spaces, and take both advantages of first order logic and the SAT techniques. Furthermore, we use an incremental search strategy to find a maximum number of disjoint idempotent quasigroups, thus decide the non-existence of large sets. The experimental results show that our method is highly efficient. The use of symmetry breaking is crucial to allow us to solve some instances in reasonable time.

Pages:16
Talk:Jul 14 14:30 (Session 96E: SAT Extensions & Applications)
Paper: