Computer Science – Logic in Computer Science
Scientific paper
2001-01-17
Theory and Practice of Logic Programming, 1(5), 591-609, 2001
Computer Science
Logic in Computer Science
19 pages, 4 figures, accepted for publication Theory and Practice of Logic Programming
Scientific paper
The well-founded semantics is one of the most widely studied and used semantics of logic programs with negation. In the case of finite propositional programs, it can be computed in polynomial time, more specifically, in O(|At(P)|size(P)) steps, where size(P) denotes the total number of occurrences of atoms in a logic program P. This bound is achieved by an algorithm introduced by Van Gelder and known as the alternating-fixpoint algorithm. Improving on the alternating-fixpoint algorithm turned out to be difficult. In this paper we study extensions and modifications of the alternating-fixpoint approach. We then restrict our attention to the class of programs whose rules have no more than one positive occurrence of an atom in their bodies. For programs in that class we propose a new implementation of the alternating-fixpoint method in which false atoms are computed in a top-down fashion. We show that our algorithm is faster than other known algorithms and that for a wide class of programs it is linear and so, asymptotically optimal.
Lonc Zbigniew
Truszczynski Miroslaw
No associations
LandOfFree
On the problem of computing the well-founded semantics 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 the problem of computing the well-founded semantics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the problem of computing the well-founded semantics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-296153