On Elementary Loops of Logic Programs

Details On Elementary Loops of Logic Programs On Elementary Loops of Logic Programs

2010-12-28

arxiv.org/abs/1012.5847v2

Computer Science

Artificial Intelligence

36 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On Elementary Loops of Logic Programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Elementary Loops of Logic Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Elementary Loops of Logic Programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-610038