On the Problem of Computing the Well-Founded Semantics

Zbigniew Lonc , Miroslaw Truszczyński


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(\\textbar\At(P)\\textbar\ × 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.
Author Zbigniew Lonc (FMIS / DAC)
Zbigniew Lonc,,
- Department of Algebra and Combinatorics
, Miroslaw Truszczyński - [University of Kentucky]
Miroslaw Truszczyński,,
Publication size in sheets0.7
Book Lloyd John, Dahl Veronica, Furbach Ulrich, Kerber Manfred, Lau Kung-Kiu, Palamidessi Catuscia, Pereira Luís Moniz, Sagiv Yehoshua, Stuckey Peter J. (eds.): Computational Logic — CL 2000, Lecture Notes In Computer Science, vol. 1861, 2000, Springer Berlin Heidelberg, ISBN 978-3-540-67797-0, [978-3-540-44957-7]
Keywords in EnglishArtificial Intelligence (incl. Robotics), Database Management, Logics and Meanings of Programs, Mathematical Logic and Formal Languages, Programming Techniques
URL https://link.springer.com/content/pdf/10.1007%2F3-540-44957-4_45.pdf
Languageen angielski
Score (nominal)10
Score sourcejournalList
Publication indicators Scopus Citations = 5; WoS Citations = 5
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?