2022/01/21 by Jo�ão Araújo, Araújo, João, Choiwah Chow +3
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Model-Driven Software Engineering Techniques #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.2201.10516
openalex publication_date 2022/01/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The enumeration of finite models is very important to the working discrete mathematician (algebra, graph theory, etc) and hence the search for effective methods to do this task is a critical goal in discrete computational mathematics. However, it is hindered by the possible existence of many isomorphic models, which usually only add noise. Typically, they are filtered out \em a posteriori, a step that might take a long time just to discard redundant models. This paper proposes a novel approach to split the generated models into mutually non-isomorphic blocks. To do that we use well-designed hand-crafted invariants as well as randomly generated invariants. The blocks are then tackled separately and possibly in parallel. This approach is integrated into Mace4 (the most popular tool among mathematicians) where it shows tremendous speed-ups for a large variety of algebraic structures.