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][4]
Three-valued logic
The well-founded semantics assigns a unique model to every general logic program. However, instead of only assigning propositionstrue or false, it adds a third value unknown for representing ignorance.[1]
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.[5]
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.[6] As of 2001[update], no general subquadratic algorithm for the problem was known.[7]
^Van Gelder, Allen; Ross, Kenneth; Schlipf, John S. (1988). "Unfounded sets and well-founded semantics for general logic programs". Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. New York, New York, USA: ACM Press. pp. 221–230. doi:10.1145/308386.308444. ISBN0897912632.
^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. 22 (6): 776–858. doi:10.1017/S1471068422000102. hdl:10174/33387. ISSN1471-0684.
