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

Answer Set Programming (ASP) is a prominent modeling and solving framework. An inconsistent core (IC) of an ASP program is an inconsistent subset of rules. In the case of inconsistent programs, a smallest or subset-minimal IC contains crucial rules for the inconsistency. In this work, we study fnding minimal ICs of ASP programs and key fragments from a complexity-theoretic perspective. Interestingly, due to ASP’s non-monotonic behavior, also consistent programs admit ICs. It turns out that there is an entire landscape of problems involving ICs with a diverse range of complexities up to the fourth level of the Polynomial Hierarchy. Deciding the existence of an IC is, already for tight programs, on the second level of the Polynomial Hierarchy. Furthermore, we give encodings for IC-related problems on the fragment of tight programs and illustrate feasibility on small instance sets.

Authors

• Johannes K. Fichte Linköping University
• Markus Hecher Massachusetts Institute of Technology Univ. Artois, CNRS, UMR 8188, Centre de Recherche en Informatique de Lens (CRIL)
• Stefan Szeider Technische Universität Wien

Keywords

• CSO: Constraint Optimization
• KRR: Computational Complexity of Reasoning
• KRR: Logic Programming
• KRR: Nonmonotonic Reasoning
• KRR: Other Foundations of Knowledge Representation & Reasoning