Complexity of super-coherence problems in ASP

DOI10.1017/S147106841300001XMaRDI QIDQ5418947zbMATH OpenOpenAlexFDO

Authors M. Alviano, Wolfgang Faber, Stefan Woltran

Publication date 30 May 2014

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.5895

zbMATH Keywords

coherenceanswer set programmingcomplexity analysisuniform equivalence

Mathematics Subject Classification ID

Logic programming (68N17)

Abstract: Adapting techniques from database theory in order to optimize Answer Set Programming (ASP) systems, and in particular the grounding components of ASP systems, is an important topic in ASP. In recent years, the Magic Set method has received some interest in this setting, and a variant of it, called DMS, has been proposed for ASP. However, this technique has a caveat, because it is not correct (in the sense of being query-equivalent) for all ASP programs. In recent work, a large fragment of ASP programs, referred to as super-coherent programs, has been identified, for which DMS is correct. The fragment contains all programs which possess at least one answer set, no matter which set of facts is added to them. Two open question remained: How complex is it to determine whether a given program is super-coherent? Does the restriction to super-coherent programs limit the problems that can be solved? Especially the first question turned out to be quite difficult to answer precisely. In this paper, we formally prove that deciding whether a propositional program is super-coherent is Pi^P_3-complete in the disjunctive case, while it is Pi^P_2-complete for normal programs. The hardness proofs are the difficult part in this endeavor: We proceed by characterizing the reductions by the models and reduct models which the ASP programs should have, and then provide instantiations that meet the given specifications. Concerning the second question, we show that all relevant ASP reasoning tasks can be transformed into tasks over super-coherent programs, even though this transformation is more of theoretical than practical interest. To appear in Theory and Practice of Logic Programming (TPLP).

Recommendations

• Dynamic magic sets and super-coherent answer set programs
• Dynamic magic sets for disjunctive Datalog programs
• Better paracoherent answer sets with less resources
• Partial compilation of ASP programs
• Max-ASP: Maximum Satisfiability of Answer Set Programs

Cites work

• scientific article; zbMATH DE number 4147465 (Why is no real title available?)
• A system of interaction and structure
• A three-valued semantics for deductive databases and logic programs
• Knowledge Representation, Reasoning and Declarative Problem Solving
• Logic programming and nonmonotonic reasoning. 8th international conference, LPNMR 2005, Diamante, Italy, September 5--8, 2005. Proceedings.
• On the complexity of regular-grammars with integer attributes
• On the computational cost of disjunctive logic programming: Propositional case
• On the power of magic
• On the relations between stable and well-founded semantics of logic programs
• Propositional semantics for disjunctive logic programs
• Succinctness as a source of complexity in logical formalisms
• Team-building with answer set programming in the Gioia-Tauro seaport
• The DLV system for knowledge representation and reasoning
• Tie-breaking semantics and structural totality
• Unfolding partiality and disjunctions in stable model semantics

Cited in

(3)

• Dynamic magic sets and super-coherent answer set programs
• Enhancing magic sets with an application to ontological reasoning
• Shared aggregate sets in answer set programming

This page was built for publication: Complexity of super-coherence problems in ASP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5418947)