Well-founded semantics

History

The well-founded semantics was defined by Van Gelder, et al. in 1988. The Prolog system XSB implements the well-founded semantics since 1997.

Three-valued logic

The well-founded semantics assigns a unique model to every general logic program. However, instead of only assigning propositions true or false, it adds a third value unknown for representing ignorance.

A simple example is the logic program that encodes two propositions a and b, and in which a must be true whenever b is not and vice versa:

a :- not(b).
b :- not(a).

neither a nor b are true or false, but both have the truth value unknown. In the two-valued stable model semantics, there are two stable models, one in which a is true and b is false, and one in which b is true and a is false.

Stratified logic programs have a 2-valued well-founded model, in which every proposition is either true or false. This coincides with the unique stable model of the program. The well-founded semantics can be viewed as a three-valued version of the stable model semantics.

Complexity

In 1989, Van Gelder suggested an algorithm to compute the well-founded semantics of a propositional logic program whose time complexity is quadratic in the size of the program. , no general subquadratic algorithm for the problem was known.

References

References

1. (July 1991). "The well-founded semantics for general logic programs". Journal of the ACM.
2. (1988). "Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems". ACM Press.
3. (November 2022). "Fifty Years of Prolog and Beyond". Theory and Practice of Logic Programming.
4. (1997). "XSB: A system for efficiently computing well-founded semantics". Springer Berlin Heidelberg.
5. Przymusinski, Teodor. ''[https://web.archive.org/web/20180108174808/https://pdfs.semanticscholar.org/3f15/0bbe37fab98974fd15afc426e879eb9b7327.pdf Well-founded Semantics Coincides with Three-Valued Stable Semantics]''. [[Fundamenta Informaticae]] XIII pp. 445-463, 1990.
6. Van Gelder, A.. (1989). "The alternating fixpoint of logic programs with negation". ACM Press.
7. (2001). "On the problem of computing the well-founded semantics". Theory and Practice of Logic Programming.