TY - GEN

T1 - On the problem of computing the well-founded semantics

AU - Lonc, Zbigniew

AU - Truszczyński, Mirosław

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.

PY - 2000

Y1 - 2000

N2 - 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(jAt(P)j × 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.

AB - 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(jAt(P)j × 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.

UR - http://www.scopus.com/inward/record.url?scp=33745436994&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33745436994&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:33745436994

T3 - Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)

SP - 673

EP - 687

BT - Computational Logic - CL 2000 - 1st International Conference, Proceedings

A2 - Dahl, Veronica

A2 - Furbach, Ulrich

A2 - Kerber, Manfred

A2 - Palamidessi, Catuscia

A2 - Stuckey, Peter J.

A2 - Pereira, Luís Moniz

A2 - Sagiv, Yehoshua

A2 - Lloyd, John

A2 - Lau, Kung-Kiu

T2 - 1st International Conference on Computational Logic, CL 2000

Y2 - 24 July 2000 through 28 July 2000

ER -