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


  • Johannes K. Fichte TU Wien, Research Unit Databases and AI, Vienna, Austria
  • Markus Hecher Computer Science and Artificial Intelligence Lab, Massachusetts Institute of Technology, Cambridge, MA, United States
  • Stefan Szeider TU Wien, Research Unit Algorithms and Complexity, Vienna, Austria



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


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.




How to Cite

Fichte, J. K., Hecher, M., & Szeider, S. (2023). Inconsistent Cores for ASP: The Perks and Perils of Non-monotonicity. Proceedings of the AAAI Conference on Artificial Intelligence, 37(5), 6363-6371.



AAAI Technical Track on Knowledge Representation and Reasoning