On the Problem of Computing the Well-Founded Semantics | SpringerLink
Skip to main content
Springer Nature Link
Log in

On the Problem of Computing the Well-Founded Semantics

  • Conference paper
  • First Online:
Computational Logic — CL 2000 (CL 2000)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 1861))

Included in the following conference series:

  • 628 Accesses

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(|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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. J.J. Alferes, C.V. Damásio, and L.M. Pereira. A logic programming system for nonmonotonic reasoning. Journal of Automated Reasoning, 14:93–147, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  2. K. Berman, J. Schlipf, and J. Franco. Computing the well-founded semantics faster. In Logic Programming and Nonmonotonic Reasoning (Lexington, KY, 1995), volume 928 of Lecture Notes in Computer Science, pages 113–125, Berlin, 1995. Springer.

    Google Scholar 

  3. S. Brass and J. Dix. Characterizations of the disjunctive well-founded semantics: confluent calculi and iterated GCWA. Journal of Automated Reasoning, 20(1):143–165, 1998.

    Article  MATH  MathSciNet  Google Scholar 

  4. S. Brass and J. Dix and B. Freitag and U. Zukowski. Transformation-based bottom-up computation of the well-founded model. Manuscript.

    Google Scholar 

  5. W. Chen, T. Swift, and D.S. Warren. Efficient top-down computation of queries under the well-founded semantics. Journal of Logic Programming, 24(3):161–199, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  6. W. Chen and D.S. Warren. Tabled evaluation with delaying for general logic programs. Journal of the ACM, 43(1):20–74, 1996.

    Article  MATH  MathSciNet  Google Scholar 

  7. W.F. Dowling and J.H. Gallier. Linear-time algorithms for testing the satisfiability of propositional Horn formulae. Journal of Logic Programming, 1(3):267–284, 1984.

    Article  MathSciNet  MATH  Google Scholar 

  8. M. C. Fitting. Fixpoint semantics for logic programming-a survey. Theoretical Computer Science, 1999. To appear.

    Google Scholar 

  9. M.C. Fitting. Well-founded semantics, generalized. In Logic programming (San Diego, CA, 1991, MIT Press Series in Logic Programming, pages 71–84, Cambridge, MA, 1991. MIT Press.

    Google Scholar 

  10. M. Gelfond and V. Lifschitz. The stable semantics for logic programs. In R. Kowalski and K. Bowen, editors, Proceedings of the 5th International Symposium on Logic Programming, pages 1070–1080, Cambridge, MA, 1988. MIT Press.

    Google Scholar 

  11. W. Marek and M. Truszczyński. Autoepistemic logic. Journal of the ACM, 38(3):588–619, 1991.

    Article  MATH  Google Scholar 

  12. I. Niemelä and P. Simons. Efficient implementation of the well-founded and stable model semantics. In Proceedings of JICSLP-96. MIT Press, 1996.

    Google Scholar 

  13. P. Rao, I.V. Ramskrishnan, K. Sagonas, T. Swift, D. S. Warren, and J. Freire. XSB: A system for efficiently computing well-founded semantics. In Proceedings of LPNMR’97, pages 430–440. Berlin: Springer-Verlag, 1997. Lecture Notes in Computer Science, 1265.

    Google Scholar 

  14. V.S. Subrahmanian, D. Nau, and C. Vago. WFS + branch bound = stable models. IEEE Transactions on Knowledge and Data Engineering, 7:362–377, 1995.

    Article  Google Scholar 

  15. A. Van Gelder. The alternating fixpoints of logic programs with negation. In ACM symposium on principles of database systems, pages 1–10, 1989.

    Google Scholar 

  16. A. Van Gelder, K.A. Ross, and J.S. Schlipf. The well-founded semantics for general logic programs. Journal of the ACM, 38(3):620–650, 1991.

    Article  MATH  Google Scholar 

  17. U. Zukowski, S. Brass, and B. Freitag. Improving the alternating fixpoint: the transformation approach. In Proceedings of LPNMR’97, pages 40–59. Berlin: Springer-Verlag, 1997. Lecture Notes in Computer Science, 1265.

    Google Scholar 

Download references

Author information

Author notes

  1. Zbigniew Lone

    Present address: Warsaw University of Technology, Poland

Authors and Affiliations

  1. Department of Computer Science, University of Kentucky, Lexington, KY, 40506-0046, USA

    Zbigniew Lone & Miroslaw Truszczyński

Authors
  1. Zbigniew Lone
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Miroslaw Truszczyński
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. The Australian National University, Australia

    John Lloyd

  2. Simon Fraser University, Canada

    Veronica Dahl

  3. Universität Koblenz, Germany

    Ulrich Furbach

  4. The University of Birmingham, UK

    Manfred Kerber

  5. University of Manchester, UK

    Kung-Kiu Lau

  6. The Pennsylvania State University, USA

    Catuscia Palamidessi

  7. Universidade Nova de Lisboa, Portugal

    Luís Moniz Pereira

  8. The Hebrew University of Jerusalem, Israel

    Yehoshua Sagiv

  9. The University of Melbourne, Australia

    Peter J. Stuckey

Rights and permissions

Reprints and permissions

Copyright information

© 2000 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Lone, Z., Truszczyński, M. (2000). On the Problem of Computing the Well-Founded Semantics. In: Lloyd, J., et al. Computational Logic — CL 2000. CL 2000. Lecture Notes in Computer Science(), vol 1861. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44957-4_45

Download citation

  • DOI: https://doi.org/10.1007/3-540-44957-4_45

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-67797-0

  • Online ISBN: 978-3-540-44957-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation