Stable model semantics: Difference between revisions

Revision as of 11:37, 12 May 2021

Revision as of 03:48, 13 October 2022

Line 99:

:<math>A \leftarrow B_{1},\dots,B_{m},\operatorname{not} C_{1},\dots,\operatorname{not} C_{n}</math>

where <math>A,B_{1},\dots,B_{m},C_{1},\dots,C_{n}</math> are ground atoms. If {{mvar|P}} does not contain negation (<math>n=0</math> in every rule of the program) then, by definition, the only stable model of {{mvar|P}} is its model that is minimal relative to set inclusion.<ref>This approach to the semantics of logic programs without negation is due to Maarten van Emden and [[Robert Kowalski]] [— {{harvnb|van Emden|Kowalski|1976]}}.</ref> (Any program without negation has exactly one minimal model.) To extend this definition to the case of programs with negation, we need the auxiliary concept of the reduct, defined as follows.

For any set {{mvar|I}} of ground atoms, the ''reduct'' of {{mvar|P}} relative to {{mvar|I}} is the set of rules without negation obtained from {{mvar|P}} by first dropping every rule such that at least one of the atoms {{tmath|C_i}} in its body

Line 205:

From the perspective of [[knowledge representation]], a set of ground atoms can be thought of as a description of a complete state of knowledge: the atoms that belong to the set are known to be true, and the atoms that do not belong to the set are known to be false. A possibly ''incomplete'' state of knowledge can be described using a consistent but possibly incomplete set of literals; if an atom <math>p</math> does not belong to the set and its negation does not belong to the set either then it is not known whether <math>p</math> is true or false.

In the context of logic programming, this idea leads to the need to distinguish between two kinds of negation&nbsp;— ''[[negation as failure]]'', discussed above, and ''strong negation'', which is denoted here by <math>\sim</math>.<ref>{{harvnb|Gelfond and |Lifschitz [|1991]}} call the second negation ''classical'' and denote it by <math>\neg</math>.</ref> The following example, illustrating the difference between the two kinds of negation, belongs to [[John McCarthy (computer scientist)|John McCarthy]]. A school bus may cross railway tracks under the condition that there is no approaching train. If we do not necessarily know whether a train is approaching then the rule using negation as failure

:<math>\hbox{Cross} \leftarrow \hbox{not Train}</math>

Line 353:

==References==

*{{cite book |first1=N. |last1=Bidoit and |first2=C. |last2=Froidevaux [1987] ''|chapter=Minimalism subsumes default logic and circumscription''. In:|chapter-url= |title=Proceedings: Symposium on Logic in Computer Science, Ithaca, New York, ofJune LICS22-8725, pages1987 |publisher=IEEE Computer Society Press |date=1987 |isbn=978-0-8186-0793-6 |id=87CH2464-6 |pages=89–97. |url=}}

* T. {{Notcite abook typo|first1=T. |last1=Eiter}} and |first2=G. |last2=Gottlob [1993]|chapter=Complexity ''[results for disjunctive logic programming and application to nonmonotonic logics |chapter-url=http://www.kr.tuwien.ac.at/staff/eiter/et-archive/ilps93.ps.gz Complexity|title=ILPS results'93: forProceedings disjunctiveof logicthe programming1993 andinternational applicationsymposium toon nonmonotonicLogic logics]''.programming In:|publisher=MIT ProceedingsPress of|date=1993 ILPS|isbn=978-93,0-262-63152-5 |pages =266–278. }}

*{{cite journal |first1=M. |last1=van Emden and [[|author2-link=Robert Kowalski |first2=R. |last2=Kowalski]] [1976] ''[http://www.doc.ic.ac.uk/~rak/papers/kowalski-van_emden.pdf |title=The semantics of predicate logic as a programming language]''. |journal=Journal of ACM, Vol. |volume=23, pages|issue= 4|pages=733–742 |date=1976 |doi=10.1145/321978.321991 |citeseerx=10.1.1.64.9246 |s2cid=11048276 |url=http://www.doc.ic.ac.uk/~rak/papers/kowalski-van_emden.pdf}}

*{{cite journal |first=F. |last=Fages [1994] ''[https://www.researchgate.net/profile/Francois_Fages/publication/220492237_Consistency_of_Clark's_completion_and_existence_of_stable_models/links/55d9a5e108aec156b9ac3f0e.pdf |title=Consistency of Clark's completion and existence of stable models]''. |journal=Journal of Methods of Logic in Computer Science, Vol. |volume=1, |issue= |pages=51–60 51–60|date=1994 |doi= |citeseerx=10.1.1.48.2157

|url=https://www.researchgate.net/publication/220492237}}

* P. Ferraris [2005] ''[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.5332&rep=rep1&type=pdf Answer sets for propositional theories]''. In: Proceedings of LPNMR-05, pages 119–131.

*{{cite book |first=P. |last=Ferraris |chapter=Answer sets for propositional theories |chapter-url=https://link.springer.com/chapter/10.1007/11546207_10 |editor= |title=Logic Programming and Nonmonotonic Reasoning. LPNMR 2005 |publisher=Springer |series=Lecture Notes in Computer Science |volume=3662 |date=2005 |isbn=978-3-540-31827-9 |pages=119–131 |doi=10.1007/11546207_10 |citeseerx=10.1.1.129.5332 |url=}}

* P. Ferraris and V. Lifschitz [2005] ''[http://www.cs.utexas.edu/users/vl/papers/mfasp.ps Mathematical foundations of answer set programming]''. In: We Will Show Them! Essays in Honour of Dov Gabbay, King's College Publications, pages 615–664.

*{{cite book |first1=P. |last1=Ferraris |first2=V. |last2=Lifschitz |chapter=Mathematical foundations of answer set programming |chapter-url=http://www.cs.utexas.edu/users/vl/papers/mfasp.ps |editor= |title=We Will Show Them! Essays in Honour of Dov Gabbay |publisher=King's College Publications |___location= |date=2005 |isbn= |pages=615–664 |citeseerx=10.1.1.79.7622}}

* M. Gelfond [1987] ''[https://www.aaai.org/Papers/AAAI/1987/AAAI87-037.pdf On stratified autoepistemic theories]''. In: Proceedings of AAAI-87, pages 207–211.

*{{cite book |first=M. |last=Gelfond |chapter=On stratified autoepistemic theories |chapter-url=https://www.aaai.org/Papers/AAAI/1987/AAAI87-037.pdf |editor= |title=AAAI'87: Proceedings of the sixth National conference on Artificial intelligence |publisher= |___location= |date=1987 |isbn=978-0-934613-42-2 |pages=207–211 |url=}}

* M. Gelfond and V. Lifschitz [1988] ''[http://www.cs.utexas.edu/users/vl/papers/stable.ps The stable model semantics for logic programming]''. In: Proceedings of the Fifth International Conference on Logic Programming (ICLP), pages 1070–1080.

*{{cite book |first1=M. |last1=Gelfond and |first2=V. |last2=Lifschitz [1991]|chapter=The ''[stable model semantics for logic programming |chapter-url=http://www.cs.utexas.edu/users/vl/papers/clnegddstable.ps Classical|title=Proceedings negationof inthe logicFifth programsInternational andConference disjunctiveon databases]''.Logic NewProgramming Generation(ICLP) Computing,|publisher=MIT Vol.Press 9,|___location= |date=1988 |isbn=978-0-262-61054-4 |pages=1070–80 365–385.|url=}}

*{{cite journal |first1=M. |last1=Gelfond |first2=V. |last2=Lifschitz |title=Classical negation in logic programs and disjunctive databases |journal=New Generation Computing |volume=9 |issue= 3–4|pages=365–385 |date=1991 |doi=10.1007/BF03037169 |url=http://www.cs.utexas.edu/users/vl/papers/clnegdd.ps |citeseerx=10.1.1.49.9332|s2cid=13036056 }}

* S. Hanks and [[Drew McDermott|D. McDermott]] [1987] ''[https://www.sciencedirect.com/science/article/pii/0004370287900439 Nonmonotonic logic and temporal projection]''. Artificial Intelligence, Vol. 33, pages 379–412.

*{{cite journal |first1=S. |last1=Hanks |author2-link=Drew McDermott |first2=D. |last2=McDermott |title=Nonmonotonic logic and temporal projection |journal=Artificial Intelligence |volume=33 |issue= 3|pages=379–412 |date=1987 |doi=10.1016/0004-3702(87)90043-9 |url=https://dx.doi.org/10.1016/0004-3702%2887%2990043-9}}

* F. Lin and Y. Zhao [2004] ''[http://www.cs.ust.hk/faculty/flin/papers/assat-aij-revised.pdf ASSAT: Computing answer sets of a logic program by SAT solvers]''. Artificial Intelligence, Vol. 157, pages 115–137.

*{{cite journal |first1=F. |last1=Lin |first2=Y. |last2=Zhao |title=ASSAT: Computing answer sets of a logic program by SAT solvers |journal=Artificial Intelligence |volume=157 |issue=1–2 |pages=115–137 |date=2004 |doi=10.1016/j.artint.2004.04.004 |s2cid=514581 |url=http://www.cs.ust.hk/faculty/flin/papers/assat-aij-revised.pdf}}

*{{cite book |first1=V. |last1=Marek and |first2=V.S. |last2=Subrahmanian [1989] ''|chapter=The relationship between logic program semantics and non-monotonic reasoning''. In|chapter-url= |title=Logic Programming: Proceedings of ICLPthe Sixth International Conference |publisher=MIT Press |date=1989 |isbn=978-89,0-262-62065-9 |pages =600–617. |url=}}

*{{cite book |first=D. |last=Pearce [1997]|chapter=A ''[new logical characterization of stable models and answer sets |chapter-url=http://ai2-s2-pdfs.s3.amazonaws.com/37f3/19f2f8af842631ff9972e1bfd91b99f93511.pdf A new logical characterization of stable models and answer sets]''. In:|editor= |title=Non-Monotonic Extensions of Logic Programming (|publisher= |series=Lecture Notes in Artificial Intelligence |volume=1216), pages|date=1997 |isbn=978-3-540-68702-3 |pages=57–70 |url= |doi=10.1007/BFb0023801 }}

* [[Raymond Reiter|R. Reiter]] [1980] ''[http://www.umiacs.umd.edu/~horty/courses/readings/reiter-default-1980.pdf A logic for default reasoning]''. Artificial Intelligence, Vol. 13, pages 81–132.

*{{cite journal |author1-link=Raymond Reiter |first=R. |last=Reiter |title=A logic for default reasoning |journal=Artificial Intelligence |volume=13 |issue= 1–2|pages=81–132 |date=1980 |doi= 10.1016/0004-3702(80)90014-4|url=http://www.umiacs.umd.edu/~horty/courses/readings/reiter-default-1980.pdf}}

[[Category:Logic programming]]