Technical Report: Inconsistency in Answer Set Programs and Extensions
This work addresses inconsistency analysis for nonmonotonic logic programs, which is incremental but relevant for ASP and its extensions like HEX-programs.
The paper tackles inconsistency in Answer Set Programming (ASP) and its HEX extension by characterizing inconsistencies, introducing explanations based on input facts, and analyzing complexity, with applications including a new query answering technique and an evaluation algorithm that shows significant, potentially exponential speedup in experiments.
Answer Set Programming (ASP) is a well-known problem solving approach based on nonmonotonic logic programs. HEX-programs extend ASP with external atoms for accessing arbitrary external information, which can introduce values that do not appear in the input program. In this work we consider inconsistent ASP- and HEX-programs, i.e., programs without answer sets. We study characterizations of inconsistency, introduce a novel notion for explaining inconsistencies in terms of input facts, analyze the complexity of reasoning tasks in context of inconsistency analysis, and present techniques for computing inconsistency reasons. This theoretical work is motivated by two concrete applications, which we also present. The first one is the new modeling technique of query answering over subprograms as a convenient alternative to the well-known saturation technique. The second application is a new evaluation algorithm for HEX-programs based on conflict-driven learning for programs with multiple components: while for certain program classes previous techniques suffer an evaluation bottleneck, the new approach shows significant, potentially exponential speedup in our experiments. Since well-known ASP extensions such as constraint ASP and DL-programs correspond to special cases of HEX, all presented results are interesting beyond the specific formalism.