Well-founded semantics

This article is about a semantics for logic programming. For the general concept in computer science, see Semantics (computer science). For other uses, see Semantics (disambiguation).

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. ^ 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.
  2. ^ 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.
  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. 22 (6): 776–858. doi:10.1017/S1471068422000102. hdl:10174/33387. ISSN 1471-0684.
  4. ^ 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{{citation}}: CS1 maint: work parameter with ISBN (link)
  5. ^ Przymusinski, Teodor. 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. 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.
  7. ^ 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.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.