Disjunctive LP + Integrity Constraints = Stable Model Semantics

Jose Alberto Fernandez, Jorge Lobo, Jack Minker and V.S. Subrahmanian

Computer Science Department
University of Maryland
College Park, Maryland 20742

The complete paper is available in:

DVI (Missing a couple of figures, embedded PostScript)
PostScript (Intact)

Abstract

We show that stable models of logic programs may be viewed as minimal models of programs that satisfy certain additional constraints. To do so, we transform the normal programs into disjunctive logic programs and sets of integrity constraints. We show that the stable models of the normal program coincide with the minimal models of the disjunctive program that satisfy the integrity constraints. As a consequence, the stable model semantics can be characterized using the Extended Generalized Closed World Assumption for disjunctive logic programs. Using this result, we develop a bottom-up algorithm for function free logic programs to find all stable models of a normal program by computing the perfect models of a disjunctive stratified logic program and checking them for consistency with the integrity constraints. The integrity constraints provide a rationale as to why some normal logic programs have no stable models.

Bibliography

[ABW88] K.R. Apt, H.A. Blair, and A. Walker. Towards a Theory of Declarative Knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 89-148. Morgan Kaufmann Pub., Washington, D.C., 1988.
[BNNS91] C. Bell, A. Nerode, R. Ng, and V.S. Subrahmanian. Computation and implementation of nonmonotonic deductive databases. Technical Report CS-TR-2801, University of Maryland, 1991. Submitted for journal publication.
[CP89] J. Cuadrado and S. Pimentel. A truth maintenance system based on stable models. In Proceedings of the 1989 North American Conference on Logic Programming, pages 274-290, 1989.
[FM91a] Jose Alberto Fernandez and Jack Minker. Bottom-up evaluation of disjunctive deductive databases. Technical report, Computer Sc. Dept., University of Maryland, 1991. In preparation.
[FM91b] Jose Alberto Fernandez and Jack Minker. Bottom-up evaluation of Hierarchical Disjunctive Deductive Databases. In Koichi Furukawa, editor, Logic Programming Proceedings of the Eighth International Conference, pages 660-675. MIT Press, 1991.
[FM91c] Jose Alberto Fernandez and Jack Minker. Computing perfect models of disjunctive stratified databases. In Don Loveland, Jorge Lobo, and Arcot Rajasekar, editors, Proceedings of the ILPS'91 Workshop on Disjunctive Logic Programs, pages 110-117, San Diego, California, October 1991. An extended version has been submitted to the Journal of Logic Programming.
[Fue91] L.O. Fuentes. Applying uncertainty formalisms to well-defined problems. Master's thesis, University of Texas at El Paso, 1991.
[GL88] M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In R.A. Kowalski and K.A. Bowen, editors, Proc. 5th International Conference and Symposium on Logic Programming, pages 1070-1080, Seattle, Washington, August 15-19 1988.
[Kow78] R.A. Kowalski. Logic for data description. In H. Gallaire J. Minker, editor, Logic and Data Bases, pages 77-102. Plenum Press, New York, 1978.
[McC80] J. McCarthy. Circumscription - a form of non-monotonic reasoning. Artificial Intelligence, 13(1 and 2):27-39, 1980.
[MS89] W. Marek and V.S. Subrahmanian. The relationship between stable, supported, default and autoepistemic semantics for general logic programs. In G. Levi and M. Martelli, editors, Proceedings of the 1989 International Conference on Logic Programming. MIT Press, 1989. Final version to appear in Theoretical Computer Science.
[MT89] W. Marek and M. Truszczynski. Stable semantics for logic programs and default theories. In E. Lusk and R. Overbeek, editors, Proceedings of the 1989 North American Conference on Logic Programming, pages 243-256. MIT Press, 1989.
[Prz86] T. Przymusinski. On the Semantics of Stratified Deductive Databases. In J. Minker, editor, Proc. Workshop on Foundations of Deductive Databases and Logic Programming, pages 433-443, Washington, D.C., August 1986.
[Prz90] T. C. Przymusinski. Extended stable semantics for normal and disjunctive programs. In D.H.D. Warren and P. Szeredi, editors, Proceedings of the 7th International Logic Programming Conference, pages 459-477, Jerusalem, 1990. MIT Press. Extended Abstract.
[Prz91] T. C. Przymusinski. Stable semantics for disjunctive programs. New Generation Computing Journal, 9:401-424, 1991. Extended Abstract appeared in [Prz90 ].
[Rei84] R. Reiter. Towards a logical reconstruction of relational database theory. In M.L. Brodie J.L. Mylopoulos J.W. Schmit, editor, On Conceptual Modelling, pages 163-189. Springer-Verlag Pub., New York, 1984.
[Rei90] R. Reiter. What should a database know? In Proceedings of the 7th International Conference on Logic Programming, page 765, Jerusalem, 1990. Abstract of Invited Talk.
[vEK76] M.H. van Emden and R.A. Kowalski. The Semantics of Predicate Logic as a Programming Language. J.ACM, 23(4):733-742, 1976.
[War91] D. S. Warren. draft manuscript, 1991.
[YH85] A. Yahya and L.J. Henschen. Deduction in Non-Horn Databases. J. Automated Reasoning, 1(2):141-160, 1985.