On elementary loops of logic programs

DOI10.1017/S1471068411000019MaRDI QIDQ2884258zbMATH OpenFDO

Authors Martin Gebser, Joohyung Lee, Yuliya Lierler

Publication date 24 May 2012

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

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

zbMATH Keywords

stable model semanticsloop formulasunfounded sets

Mathematics Subject Classification ID

Logic programming (68N17)

Abstract: Using the notion of an elementary loop, Gebser and Schaub refined the theorem on loop formulas due to Lin and Zhao by considering loop formulas of elementary loops only. In this article, we reformulate their definition of an elementary loop, extend it to disjunctive programs, and study several properties of elementary loops, including how maximal elementary loops are related to minimal unfounded sets. The results provide useful insights into the stable model semantics in terms of elementary loops. For a nondisjunctive program, using a graph-theoretic characterization of an elementary loop, we show that the problem of recognizing an elementary loop is tractable. On the other hand, we show that the corresponding problem is {sf coNP}-complete for a disjunctive program. Based on the notion of an elementary loop, we present the class of Head-Elementary-loop-Free (HEF) programs, which strictly generalizes the class of Head-Cycle-Free (HCF) programs due to Ben-Eliyahu and Dechter. Like an HCF program, an HEF program can be turned into an equivalent nondisjunctive program in polynomial time by shifting head atoms into the body.

Recommendations

• Head-Elementary-Set-Free Logic Programs
• On the complexity of identifying head-elementary-set-free programs
• Logic Programming
• Logic Programming and Nonmonotonic Reasoning
• Computing loops with at most one external support rule for disjunctive logic programs

Cites work

• ASSAT: computing answer sets of a logic program by SAT solvers
• Alternative Characterizations for Program Equivalence under Answer-Set Semantics Based on Unfounded Sets
• Disjunctive stable models: Unfounded sets, fixpoint semantics, and computation
• Enhancing disjunctive logic programming systems by SAT checkers
• Head-Elementary-Set-Free Logic Programs
• Logic programming and knowledge representation
• Loop formulas for circumscription
• Negation as failure in the head
• Nested expressions in logic programs
• On Reductive Semantics of Aggregates in Answer Set Programming
• On the complexity of identifying head-elementary-set-free programs
• On the computational cost of disjunctive logic programming: Propositional case
• Propositional semantics for disjunctive logic programs
• Some (in)translatability results for normal logic programs and propositional theories
• Stable models and circumscription
• The DLV system for knowledge representation and reasoning
• Tight logic programs
• Unfolding partiality and disjunctions in stable model semantics
• Why are there so many loop formulas?

Cited in

(9)

• Aspmc: new frontiers of algebraic answer set counting
• Stepwise debugging of answer-set programs
• Paracoherent answer set semantics meets argumentation frameworks
• Computing loops with at most one external support rule for disjunctive logic programs
• Reasoning with recursive loops under the PLP framework
• Computationally hard problems for logic programs under answer set semantics
• Head-Elementary-Set-Free Logic Programs
• Logic Programming and Nonmonotonic Reasoning
• Graph-based construction of minimal models

Describes a project that uses

Uses Software

• ASSAT

This page was built for publication: On elementary loops of logic programs

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