On the problem of computing the well-founded semantics

Zbigniew Lonc, Mirosław Truszczyński

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

11 Scopus citations


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.

Original languageEnglish
Title of host publicationComputational Logic - CL 2000 - 1st International Conference, Proceedings
EditorsVeronica Dahl, Ulrich Furbach, Manfred Kerber, Catuscia Palamidessi, Peter J. Stuckey, Luís Moniz Pereira, Yehoshua Sagiv, John Lloyd, Kung-Kiu Lau
Number of pages15
ISBN (Electronic)3540677976, 9783540677970
StatePublished - 2000
Event1st International Conference on Computational Logic, CL 2000 - London, United Kingdom
Duration: Jul 24 2000Jul 28 2000

Publication series

NameLecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
ISSN (Print)0302-9743


Conference1st International Conference on Computational Logic, CL 2000
Country/TerritoryUnited Kingdom

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On the problem of computing the well-founded semantics'. Together they form a unique fingerprint.

Cite this