Well-founded semantics
In this article we are going to delve into the topic of Well-founded semantics, a topic that has captured the attention of people of all ages and interests. Well-founded semantics has been the subject of debate and discussion in various areas, whether in the academic, social, political or cultural spheres. Since its emergence, Well-founded semantics has aroused great interest due to its relevance in today's society and its impact on our lives. Throughout this article, we will explore different perspectives and approaches related to Well-founded semantics, with the aim of providing a comprehensive and enriching vision on this topic.
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
- ^ a b 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.
- ^ 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. 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; 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. 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, vol. 1265, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 430–440, doi:10.1007/3-540-63255-7_33, ISBN 978-3-540-63255-9, 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. 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.
- ^ Lonc, Zbigniew; Truszczyński, Mirosław (2001). "On the problem of computing the well-founded semantics". Theory and Practice of Logic Programming. 1 (5): 591–609. arXiv:cs/0101014. doi:10.1017/S1471068401001053. ISSN 1471-0684.