An ASP-Based Framework for MUSes
Mohimenul Kabir, Kuldeep S Meel · 2025
Read An ASP-Based Framework for MUSes by Mohimenul Kabir, Kuldeep S Meel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-03929.txt.
Introduction
Kabir and Meel target a diagnostic problem in logic: when a formula cannot be satisfied, which small set of clauses is already impossible on its own? Such minimal unsatisfiable subsets explain failures in verification and design, but finding many of them, or counting them all, is expensive.
Their framework, MUS-ASP, rewrites the search as an answer set program, letting a modern solver stream out these subsets one by one in an online fashion. The encoding leans on the solver's strength with combinatorial structure. In wide tests, the approach sped up both listing and counting, and it gained further when plugged into hybrid solvers, including one the authors built around it.
Catalog record
| CREATOR | Mohimenul Kabir, Kuldeep S Meel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-03929
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An ASP-Based Framework for MUSes Mohimenul Kabir, Kuldeep S Meel Abstract Given an unsatisfiable formula, understanding the core reason for unsatisfiability is crucial in several applications. One effective way to capture this is through the minimal unsatisfiable subset (MUS), the subset-minimal set of clauses that remains unsatisfiable. Current research broadly focuses on two directions: (i) enumerating as many MUSes as possible within a given time limit, and (ii) counting the total number of MUSes for a given unsatisfiable formula. In this paper, we introduce an answer set programming-based framework, named 𝖬 𝖴 𝖲 \mathsf{\mathchar 29005\mathchar 29013\mathchar 29011} - 𝖠 𝖲 𝖯 \mathsf{\mathchar 28993\mathchar 29011\mathchar 29008} , designed for online enumeration of MUSes. ASP is a powerful tool for its strengths in knowledge representation and is particularly suitable for specifying complex combinatorial problems. By translating MUS enumeration into answer set solving, 𝖬 𝖴 𝖲 \mathsf{\mathchar 29005\mathchar 29013\mathchar 29011} - 𝖠 𝖲 𝖯 \mathsf{\mathchar 28993\mathchar 29011\mathchar 29008} leverages the computational efficiency of state-of-the-art ASP systems. Our extensive experimental evaluation demonstrates the effectiveness of 𝖬 𝖴 𝖲 \mathsf{\mathchar 29005\mathchar 29013\mathchar 29011} - 𝖠 𝖲 𝖯 \mathsf{\mathchar 28993\mathchar 29011\mathchar 29008} and highlights the acceleration in both MUS enumeration and counting tasks, particularly when integrated within hybrid solvers, including the framework proposed in this paper. keywords Minimal Unsatisfiable Subset, MUS Enumeration, MUS Counting, Answer Set Enumeration 1 Introduction When dealing with an unsatisfiable formula — one that has no solution — it is often crucial to identify the reasons for its unsatisfiability. A common concept in the literature is the minimal unsatisfiable subset (MUS), which provides a concise explanation for the formula’s unsatisfiability ( Liffiton et al., 2016 ) . For instance, in requirement analysis ( Bendík, 2017 ) , a set of constraints represents the requirements that need to be fulfilled. If these constraints are unsatisfiable, a MUS highlights the minimal set of requirements that cannot be satisfied simultaneously. Given an unsatisfiable Boolean formula \mathchar 28998 , expressed as a conjunction of clauses \{\mathchar 28995_{\mathchar 28721}\mathchar 24891\ldots\mathchar 24891\mathchar 28995_{\mathsf{\mathchar 29038\mathchar 29027\mathchar 29036}}\} , a minimal unsatisfiable subset (MUS) of \mathchar 28998 is a subset \mathchar 28998\raise 3.44444pt\hbox{\sevensy\char 48\relax}\mathchar 12818\mathchar 28998 such that \mathchar 28998\raise 3.44444pt\hbox{\sevensy\char 48\relax} is unsatisfiable and for every \mathchar 28995_{\mathchar 29033}\mathchar 12850\mathchar 28998\raise 3.44444pt\hbox{\sevensy\char 48\relax} , the set \mathchar 28998\raise 3.44444pt\hbox{\sevensy\char 48\relax}\mathchar 8814\{\mathchar 28995_{\mathchar 29033}\} is satisfiable. Finding MUSes is an active research area due to their wide range of applications, including formal equivalence checking ( Cohen et al., 2010 ) , Boolean function bi-decomposition ( Chen and Marques-Silva, 2012 ) , counter-example guided abstraction refinement ( Andraus et al., 2007 ) , circuit error diagnosis ( Han and Lee, 1999 ) , and others ( Hunter and Konieczny, 2008 ; Ivrii et al., 2016 ; Jannach and Schmitz, 2016 ) . Since the MUS of an unsatisfiable formula is not necessarily unique, it is important to enumerate multiple MUSes. Enumerating more MUSes of \mathchar 28998 provides a clearer explanation of the underlying unsatisfiability ( Bendík and Černá, 2020b ) . Thus, existing research focuses on enumerating MUSes in an online fashion ( Bacchus and Katsirelos, 2015 ; Katsirelos and Bacchus, 2016 ; Bendík and Černá, 2020b ; Bendík et al., 2018 ; Narodytska et al., 2018 ; Liffiton and Malik, 2013 ) , aiming to identify as many MUSes as possible within a given time limit. Moreover, the number of MUSes is frequently used as a metric to quantify inconsistency in diagnostic tasks ( Mu et al., 2011 ; Hunter and Konieczny, 2008 ) . Existing MUS enumeration algorithms can be broadly divided into two categories: algorithms based on the well-known seed-shrink scheme ( Bendík and Černá, 2020a ) and those employing the hitting set duality ( Reiter, 1987 ) . The seed-shrink scheme systematically explores subsets of \mathchar 28998 and identifies an unsatisfiable subset called a u-seed , which is then shrunk into a MUS through a single MUS extractor ( Belov and Marques-Silva, 2012 ) . Conversely, the hitting set duality leverages the well-known relationship between MUSes and MCSes, where a minimal correction subset (MCS) is the minimal subset \mathchar 28998\raise 3.44444pt\hbox{\sevensy\char 48\relax}\mathchar 12826\mathchar 28998 such that the formula \mathchar 28998\mathchar 8814\mathchar 28998\raise 3.44444pt\hbox{\sevensy\char 48\relax} is satisfiable. This approach involves computing and exploiting the MCSes of \mathchar 28998 to enumerate MUSes ( Liffiton and Sakallah, 2008 ) . Traditional MUS enumeration techniques often rely on SAT-based methods. In contrast, we explore an alternative perspective by formulating MUS enumeration as an answer set solving problem, leveraging the expressiveness of ASP for modeling combinatorial structures. Answer set programming (ASP) ( Marek and Truszczyński, 1999 ) is a well-known declarative problem-solving paradigm in knowledge representation and reasoning, valued for its ability to model complex combinatorial problems ( Erdem et al., 2016 ) . An ASP program consists of logical rules defined over propositional atoms , encoding domain knowledge and queries. An assignment of values to propositional atoms that satisfies the ASP semantics of the program is referred to as an answer set . ASP programs can be classified into two categories based on their expressiveness: disjunctive and normal ASP programs ( Lierler, 2005 ) . However, the expressiveness comes at the cost of computational complexity. Specifically, determining whether a disjunctive program has an answer set is \textstyle\mathchar 4944\displaylimits_{\mathchar 28722}^{\mathchar 29008} -complete ( Eiter and Gottlob, 1995 ) , while the complexity reduces to NP-complete for normal programs ( Marek and Truszczyński, 1991 ) . The main contribution of the paper is the proposal of an ASP solving-based MUS enumeration framework called \mathsf{\mathchar 29005\mathchar 29013\mathchar 29011} - \mathsf{\mathchar 28993\mathchar 29011\mathchar 29008} . At a high level, given an unsatisfiable Boolean formula \mathchar 28998 , we formulate a disjunctive ASP program \mathcal{\mathchar 29008}_{\mathchar 28998} such that the answer sets of \mathcal{\mathchar 29008}_{\mathchar 28998} correspond to the unsatisfiable cores of \mathchar 28998 . To compute MUSes, we focus on subset minimal answer sets with respect to a target set of atoms. Computing the subset minimal answer sets is not a new research problem ( Gebser et al., 2013 ; Alviano et al., 2023 ; Brewka et al., 2015 ) ; it has been shown to be useful in addressing various real-world computational problems ( Ostrowski et al., 2016 ; Amendola et al., 2021 ; Dodaro et al., 2019 ) . We are not the first to leverage ASP for MUS computation; it has previously been used to compute MUSes of LTL f ( Ielo et al., 2025 ) . Particularly, we harness the efficiency of subset minimal answer set solvers to compute MUSes. Moreover, we incorporate several heuristics into our encoding to enhance practical scalability. Although the worst-case complexity of disjunctive ASP is high ( \textstyle\mathchar 4944\displaylimits_{\mathchar 28722}^{\mathchar 29008} -complete), practical instances often admit a small backdoor to normality ( Fichte and Szeider, 2015 ) , meaning that they can be transformed into normal programs by few atoms. From the computational complexity perspective, finding a MUS is in \text{FP}^{\text{NP}} ( Chen and Toda, 1995 ; Marques-Silva and Janota, 2014 ) . It is worth noting that reducing one problem to a harder one is not uncommon in combinatorial problem-solving ( Latour et