well-founded semantics

The well-founded semantics was defined by Van Gelder, et al. in 1988.{{Cite journal |last1=Van Gelder |first1=Allen |last2=Ross |first2=Kenneth A. |last3=Schlipf |first3=John S. |date=July 1991 |title=The well-founded semantics for general logic programs |url=http://dx.doi.org/10.1145/116825.116838 |journal=Journal of the ACM |volume=38 |issue=3 |pages=619–649 |doi=10.1145/116825.116838 |issn=0004-5411|url-access=subscription }}{{Cite book |last1=Van Gelder |first1=Allen |last2=Ross |first2=Kenneth |last3=Schlipf |first3=John S. |chapter=Unfounded sets and well-founded semantics for general logic programs |date=1988 |title=Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems |pages=221–230 |location=New York, New York, USA |publisher=ACM Press |doi=10.1145/308386.308444|doi-access=free |isbn=0897912632 }} The Prolog system XSB implements the well-founded semantics since 1997.{{Cite journal |last1=Körner |first1=Philipp |last2=Leuschel |first2=Michael |last3=Barbosa |first3=João |last4=Costa |first4=Vítor Santos |last5=Dahl |first5=Verónica |last6=Hermenegildo |first6=Manuel V. |last7=Morales |first7=Jose F. |last8=Wielemaker |first8=Jan |last9=Diaz |first9=Daniel |last10=Abreu |first10=Salvador |last11=Ciatto |first11=Giovanni |date=November 2022 |title=Fifty Years of Prolog and Beyond |journal=Theory and Practice of Logic Programming |language=en |volume=22 |issue=6 |pages=776–858 |doi=10.1017/S1471068422000102 |issn=1471-0684|doi-access=free |hdl=10174/33387 |hdl-access=free }}{{Citation |last1=Rao |first1=Prasad |title=XSB: A system for efficiently computing well-founded semantics |date=1997 |url=http://link.springer.com/10.1007/3-540-63255-7_33 |work=Logic Programming And Nonmonotonic Reasoning |volume=1265 |pages=430–440 |editor-last=Dix |editor-first=Jürgen |access-date=2023-11-17 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/3-540-63255-7_33 |isbn=978-3-540-63255-9 |last2=Sagonas |first2=Konstantinos |last3=Swift |first3=Terrance |last4=Warren |first4=David S. |last5=Freire |first5=Juliana |editor2-last=Furbach |editor2-first=Ulrich |editor3-last=Nerode |editor3-first=Anil|url-access=subscription }}

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.Przymusinski, Teodor. [https://web.archive.org/web/20180108174808/https://pdfs.semanticscholar.org/3f15/0bbe37fab98974fd15afc426e879eb9b7327.pdf Well-founded Semantics Coincides with Three-Valued Stable Semantics]. Fundamenta Informaticae XIII pp. 445-463, 1990.

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.{{Cite conference |last=Van Gelder |first=A. |date=1989 |title=The alternating fixpoint of logic programs with negation |url=http://portal.acm.org/citation.cfm?doid=73721.73722 |language=en |publisher=ACM Press |pages=1–10 |doi=10.1145/73721.73722 |isbn=978-0-89791-308-9|doi-access=free |conference = Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems}} {{As of|2001}}, no general subquadratic algorithm for the problem was known.{{Cite journal |last1=Lonc |first1=Zbigniew |last2=Truszczyński |first2=Mirosław |date=2001 |title=On the problem of computing the well-founded semantics |url=https://www.cambridge.org/core/product/identifier/S1471068401001053/type/journal_article |journal=Theory and Practice of Logic Programming |language=en |volume=1 |issue=5 |pages=591–609 |doi=10.1017/S1471068401001053 |issn=1471-0684|arxiv=cs/0101014 }}

{{reflist}}

Category:Logic programming