4 papers · 1 filter
Breaking Symmetries with Involutions
Michael Codish, Mikoláš Janota
Symmetry breaking for graphs and other combinatorial objects is notoriously hard. On the one hand, complete symmetry breaks are exponential in size. On the other hand, current, sta…
Breaking Symmetries from a Set-Covering Perspective
Michael Codish, Mikoláš Janota
We formalize symmetry breaking as a set-covering problem. For the case of breaking symmetries on graphs, a permutation covers a graph if applying it to the graph yields a smaller g…
Complete Symmetry Breaking for Finite Models
Marek DanÄo, Mikoláš Janota, Michael Codish +1
This paper introduces a SAT-based technique that calculates a compact and complete symmetry-break for finite model finding, with the focus on structures with a single binary operat…
SAT-Based Techniques for Lexicographically Smallest Finite Models
Mikoláš Janota, Choiwah Chow, João Araújo +2
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 e…