Well-founded semantics explained

In computer science, the well-founded semantics is a three-valued semantics for logic programming, which gives a precise meaning to general logic programs.

History

The well-founded semantics was defined by Van Gelder, et al. in 1988.^{[1] [2]} The Prolog system XSB implements the well-founded semantics since 1997.^[3]

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.^[4]

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.^[5], no general subquadratic algorithm for the problem was known.^[6]

Notes and References

1. Van Gelder . Allen . Ross . Kenneth A. . Schlipf . John S. . July 1991 . The well-founded semantics for general logic programs . Journal of the ACM . 38 . 3 . 619–649 . 10.1145/116825.116838 . 0004-5411.
2. Book: Van Gelder . Allen . Ross . Kenneth . Schlipf . John S. . Unfounded sets and well-founded semantics for general logic programs . 1988 . Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems . 221–230 . New York, New York, USA . ACM Press . 10.1145/308386.308444. free . 0897912632 .
3. Körner . Philipp . Leuschel . Michael . Barbosa . João . Costa . Vítor Santos . Dahl . Verónica . Hermenegildo . Manuel V. . Morales . Jose F. . Wielemaker . Jan . Diaz . Daniel . Abreu . Salvador . Ciatto . Giovanni . November 2022 . Fifty Years of Prolog and Beyond . Theory and Practice of Logic Programming . en . 22 . 6 . 776–858 . 10.1017/S1471068422000102 . 1471-0684. free . 10174/33387 . free .
4. Przymusinski, Teodor. Well-founded Semantics Coincides with Three-Valued Stable Semantics. Fundamenta Informaticae XIII pp. 445-463, 1990.
5. Van Gelder . A. . 1989 . The alternating fixpoint of logic programs with negation . en . ACM Press . 1–10 . 10.1145/73721.73722 . 978-0-89791-308-9. free . Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems.
6. Lonc . Zbigniew . Truszczyński . Mirosław . 2001 . On the problem of computing the well-founded semantics . Theory and Practice of Logic Programming . en . 1 . 5 . 591–609 . 10.1017/S1471068401001053 . 1471-0684. cs/0101014 .