Inconsistent Cores for ASP: The Perks and Perils of Non-monotonicity

Johannes Klaus Fichte, Markus Hecher, Stefan SzeiderAAAI 2023 · DOI

Abstract

In Boolean Satisfiability (SAT), identifying Minimal Unsatisfiable Subsets (MUSes) is a standard technique for debugging. This paper extends this concept to Answer Set Programming (ASP) through "Inconsistent Cores" (ICs). Due to the non-monotonic nature of ASP, even consistent programs can harbor inconsistent subsets, leading to a significantly more complex computational landscape. We provide a comprehensive complexity analysis and demonstrate that finding the smallest inconsistent cores (SMICs) is practically feasible and provides superior diagnostic value compared to standard minimal cores.

Introduction

In traditional monotonic logic, if a set of formulas is consistent, all its subsets are also consistent. Answer Set Programming (ASP) breaks this rule. Because adding a rule can eliminate answer sets, a program might be consistent as a whole while containing a subset of rules that, in isolation, has no solutions. These subsets are termed Inconsistent Cores (ICs).

Identifying ICs is crucial for debugging complex ASP encodings. However, the non-monotonicity that makes ASP powerful also makes finding these cores computationally expensive. This research explores the theoretical boundaries and practical implementations for identifying various types of cores, including Minimal ICs (MICs) and the Smallest MICs (SMICs).

Theoretical Complexity Landscape

The researchers categorized the difficulty of finding ICs across different ASP fragments. The complexity varies significantly depending on whether the program is "tight" (no recursion through negation), "normal," or "disjunctive."

Complexity map of existence and reasoning problems for various ASP fragments.

As shown in the complexity map above, reasoning with these cores in disjunctive programs can reach the fourth level of the Polynomial Hierarchy ($\Sigma^P_4$). This jump in complexity is driven fundamentally by non-monotonicity rather than simple recursion.

Methodology: Meta-Encodings and Saturation

To address these high-complexity problems, the authors developed meta-encodings—ASP programs designed to process other ASP programs. A key technique used is saturation, which allows the solver to verify the inconsistency of a "guessed" core by checking that all possible variable assignments fail to produce a valid answer set.

For identifying the Smallest MIC (SMIC), the researchers utilized the optimization features of the clingo solver. By using #minimize statements, the solver can search for the core with the minimum number of rules, which is often the most useful for human developers.

Experimental Evaluation

The approach was tested on problem domains from the PACE 2016 and 2017 challenges, including reachability, edge coloring, and vertex coloring. The experiments focused on comparing the size and computation time for different types of cores.

Experimental results comparing execution time and core size across different instance sets.

The results indicate a significant advantage for SMICs. In the reachability domain (S1), the median size of an SMIC was only 84 rules, compared to 632 rules for standard minimal cores (RIC/EIC). Despite the higher theoretical complexity of finding the smallest core, the actual running times were remarkably similar to finding any minimal core, demonstrating the efficiency of modern ASP optimization.

Conclusion

The study reveals a "consistency paradox" in ASP: consistent programs can contain inconsistent cores. While this introduces significant computational challenges—up to $\Sigma^P_4$ complexity—practical meta-encoding techniques remain effective for medium-sized instances. The finding that SMICs are substantially smaller than MICs without a prohibitive performance penalty suggests that seeking the smallest core is the preferred strategy for ASP debugging and optimization. Future work may involve leveraging Quantified Boolean Formula (QBF) solvers to handle the most complex disjunctive cases.

Summary updated

BibTeX
@inproceedings{fichte2023inconsistent,
  author = {Johannes Klaus Fichte and Markus Hecher and Stefan Szeider},
  title = {{Inconsistent Cores for ASP: The Perks and Perils of Non-monotonicity}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25783},
}
Figure