Computing Stable and Partial Stable Models of Extended Disjunctive Logic Programs

Department of Computer Science

Institute for Advanced Computer Studies

University of Maryland, College Park, MD 20742, USA.

Carolina Ruiz

Jack Minker

The complete paper is available in:

• DVI
• PostScript

Abstract

In [Prz91], Przymusinski introduced the partial (or 3-valued) stable model semantics which extends the (2-valued) stable model semantics defined originally by Gelfond and Lifschitz [GL88]. In this paper we describe a procedure to compute the collection of all partial stable models of an extended disjunctive logic program. This procedure consists in transforming an extended disjunctive logic program into a constrained disjunctive program free of negation-by-default whose set of 2-valued minimal models corresponds to the set of partial stable models of the original program.

Bibliography

• [AHU83] A. Aho, J. Hopcroft, and J. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983.
• [BNNS93] C. Bell, A. Nerode, R. Ng, and V.S. Subrahmanian. Implementing stable model semantics by linear programming. In Proceedings of the 1993 International Workshop on Logic Programming and Non-monotonic Reasoning, June 1993.
• [EG93] T. Eiter and G. Gottlob. Complexity aspects of various semantics for disjunctive databases. In Proceedings of the Twelfth ACM SIGART-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-93), pages 158-167. ACM Press, May 1993.
• [Fag91] F. Fages. A new fixpoint semantics for general logic programs compared with the well-founded and the stable model semantics. New Generation Computing, 9:425-443, 1991.
• [Fit85] M. Fitting. A Kripke-Kleene semantics of logic programs. Journal of Logic Programming, 2(4):295-312, December 1985.
• [Fit93] M. Fitting. The family of stable models. Journal of Logic Programming, 17(2, 3 & 4):197-226, 1993.
• [FLMS93] Jose Alberto Fernandez, J. Lobo, Jack Minker, and V.S. Subrahmanian. Disjunctive lp + integrity constrains = stable model semantics. Annals of Mathematics and Artificial Intelligence, 8(3-4):449-474, 1993.
• [GL88] M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In R. Kowalski and K. Bowen, editors, Proceedings of the Fifth International Conference and Symposium on Logic Programming, pages 1070-1080, Seattle, WA, USA, Aug. 1988. The MIT Press.
• [IKH92] K. Inoue, M. Koshimura, and R. Hasegawa. Embedding negation as failure into a model generation theorem prover. In D. Kapur, editor, Proceedings of the Eleventh International Conference on Automated Deduction, pages 400-415, Saratoga Springs NY, USA, June 1992. Springer-Verlag.
• [MR90] Jack Minker, and A. Rajasekar. A fixpoint semantics for disjunctive logic programs. Journal of Logic Programming, 9(1):45-74, July 1990.
• [MR93] Jack Minker and Carolina Ruiz. On extended disjunctive logic programs. In J. Komorowski and Z.W. Ras, editors, Proceedings of the Seventh International Symposium on Methodologies for Intelligent Systems, pages 1-18. Lecture Notes in AI. Springer-Verlag, June 1993. (Invited Paper).
• [MR94] Jack Minker and Carolina Ruiz. Semantics for disjunctive logic programs with explicit and default negation. Fundamenta Informaticae, 20(3/4):145-192, 1994. Anniversary Issue edited by H. Rasiowa.
• [Prz91] T. C. Przymusinski. Stable semantics for disjunctive programs. New Generation Computing, 9:401-424, 1991.