On elementary loops of logic programs
From MaRDI portal
Publication:2884258
DOI10.1017/S1471068411000019zbMATH Open1242.68050arXiv1012.5847MaRDI QIDQ2884258FDOQ2884258
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)
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.
Full work available at URL: https://arxiv.org/abs/1012.5847
Recommendations
Cites Work
- ASSAT: computing answer sets of a logic program by SAT solvers
- On the computational cost of disjunctive logic programming: Propositional case
- Propositional semantics for disjunctive logic programs
- Nested expressions in logic programs
- The DLV system for knowledge representation and reasoning
- Stable models and circumscription
- Logic programming and knowledge representation
- Unfolding partiality and disjunctions in stable model semantics
- Disjunctive stable models: Unfounded sets, fixpoint semantics, and computation
- On the complexity of identifying head-elementary-set-free programs
- Head-Elementary-Set-Free Logic Programs
- Loop formulas for circumscription
- Tight logic programs
- On Reductive Semantics of Aggregates in Answer Set Programming
- Negation as failure in the head
- Why are there so many loop formulas?
- Enhancing disjunctive logic programming systems by SAT checkers
- Some (in)translatability results for normal logic programs and propositional theories
- Alternative Characterizations for Program Equivalence under Answer-Set Semantics Based on Unfounded Sets
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
Uses Software
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)
