Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-25T05:01:52.308Z Has data issue: false hasContentIssue false
  • English
  • Français

On the problem of computing the well-founded semantics

Published online by Cambridge University Press:  22 October 2001

ZBIGNIEW LONC  and
MIROSŁAW TRUSZCZYŃSKI
ZBIGNIEW LONC
Affiliation:
Department of Computer Science, University of Kentucky, Lexington, KY 40506-0046, USA (e-mail: [email protected], [email protected])
MIROSŁAW TRUSZCZYŃSKI
Affiliation:
Department of Computer Science, University of Kentucky, Lexington, KY 40506-0046, USA (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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([mid ]At(P)[mid ] × 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.

Keywords

well-founded semanticsalternating fixpoint
Type
Research Article
Information
Theory and Practice of Logic Programming , Volume 1 , Issue 5 , September 2001 , pp. 591 - 609
Copyright
© 2001 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

A preliminary version of this paper appeared in the Proceedings of Computational Logic – CL 2000, Lecture Notes in Artificial Intelligence, 1861, Springer-Verlag, 2000.