Stable model semantics: Difference between revisions

Revision as of 15:13, 26 May 2011

Revision as of 19:39, 2 August 2012

Line 354:

The program above has one more stable model, <math>\{q\}</math>.

As in the case of traditional programs, each element of any stable model of a disjunctive program <math>P</math> is a head atom of <math>P</math>, in the sense that it occurs in the head of one of the rules of <math>P</math>. As in the traditional case, the stable models of a disjunctive program are minimal and form an antichain. Testing whether a finite disjunctive program has a stable model is [[Polynomial hierarchy|<math>\Sigma_2^{\rm P}</math>-complete]] [{{Not a typo|Eiter}} and Gottlob, 1993].

==Stable models of a set of propositional formulas==

Line 398:

* N. Bidoit and C. Froidevaux [1987] ''Minimalism subsumes default logic and circumscription''. In: Proceedings of LICS-87, pages 89-97.

* T. {{Not a typo|Eiter}} and G. Gottlob [1993] ''[http://www.kr.tuwien.ac.at/staff/eiter/et-archive/ilps93.ps.gz Complexity results for disjunctive logic programming and application to nonmonotonic logics]''. In: Proceedings of ILPS-93, pages 266-278.

* M. van Emden and [[Robert Kowalski|R. Kowalski]] [1976] ''[http://www.doc.ic.ac.uk/~rak/papers/kowalski-van_emden.pdf The semantics of predicate logic as a programming language]''. Journal of ACM, Vol. 23, pages 733-742.