Well-founded semantics
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][4]
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.[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), no general subquadratic algorithm for the problem was known.[7]
References
- ↑ 1.0 1.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. doi:10.1145/116825.116838. ISSN 0004-5411. http://dx.doi.org/10.1145/116825.116838.
- ↑ 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 - PODS '88 (New York, New York, USA: ACM Press): 221–230. doi:10.1145/308386.308444. ISBN 0897912632.
- ↑ Körner, Philipp; Leuschel, Michael; Barbosa, João; Costa, Vítor Santos; Dahl, Verónica; Hermenegildo, Manuel V.; Morales, Jose F.; Wielemaker, Jan et al. (November 2022). "Fifty Years of Prolog and Beyond" (in en). Theory and Practice of Logic Programming 22 (6): 776–858. doi:10.1017/S1471068422000102. ISSN 1471-0684.
- ↑ Rao, Prasad; Sagonas, Konstantinos; Swift, Terrance; Warren, David S.; Freire, Juliana (1997), Dix, Jürgen; Furbach, Ulrich; Nerode, Anil, eds., "XSB: A system for efficiently computing well-founded semantics", Logic Programming And Nonmonotonic Reasoning (Berlin, Heidelberg: Springer Berlin Heidelberg) 1265: pp. 430–440, doi:10.1007/3-540-63255-7_33, ISBN 978-3-540-63255-9, http://link.springer.com/10.1007/3-540-63255-7_33, retrieved 2023-11-17
- ↑ Przymusinski, Teodor. Well-founded Semantics Coincides with Three-Valued Stable Semantics. Fundamenta Informaticae XIII pp. 445-463, 1990.
- ↑ Van Gelder, A. (1989). "The alternating fixpoint of logic programs with negation" (in en). Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. ACM Press. pp. 1–10. doi:10.1145/73721.73722. ISBN 978-0-89791-308-9. http://portal.acm.org/citation.cfm?doid=73721.73722.
- ↑ Lonc, Zbigniew; Truszczyński, Mirosław (2001). "On the problem of computing the well-founded semantics" (in en). Theory and Practice of Logic Programming 1 (5): 591–609. doi:10.1017/S1471068401001053. ISSN 1471-0684. https://www.cambridge.org/core/product/identifier/S1471068401001053/type/journal_article.
 |  |
