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 thatsatisfy the integrity constraints. As a consequence, the stable model semantics can be characterized using theextended generalized closed world assumption for disjunctive logic programs. Using this result, we develop a bottomup 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.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
K.R. Apt, H.A. Blair and A. Walker, Towards a theory of declarative knowledge, in:Foundations of Deductive Databases and Logic Programming, ed. J. Minker (Morgan Kaufmann, Washington, D.C., 1988) pp. 89–148.
C. Bell, A. Nerode, R. Ng and V.S. Subrahmanian, Computation and implementation of non-monotonic deductive databases, Technical Report CS-TR-2801, University of Maryland (1991). Submitted for journal publication.
J. Cuadrado and S. Pimentel, A truth maintenance system based on stable models, in:Proc. 1989 North American Conf. on Logic Programming (1989) pp. 274–290.
J.A. Fernández and J. Minker, Bottom-up evaluation of disjunctive deductive databases, Technical Report, Computer Science Department, University of Maryland (1991), in preparation.
J.A. Fernández and J. Minker, Bottom-up evaluation of hierarchical disjunctive deductive databases, in:Proc. 8th Int. Conf. on Logic Programming, ed. K. Furukawa (MIT Press, 1991).
J.A. Fernández and J. Minker, Computing perfect models of disjunctive stratified databases, in:Proc. ILPS'91 Workshop on Disjunctive Logic Programs, San Diego, CA (October 1991), ed. D. Loveland et al., pp. 110–117. An extended version has been submitted to Annals of Mathematical Artificial Intelligence.
L.O. Fuentes, Applying uncertainty formalisms to well-defined problems, Master's Thesis, University of Texas at El Paso (1991).
M. Gelfond and V. Lifschitz, The stable model semantics for logic programming, in:Proc. 5th Int. Conf. and Symp. on Logic Programming, Seattle, Washington (August, 1988), ed. R.A. Kowalski and K.A. Bowen, pp. 1070–1080.
R.A. Kowalski, Logic for data description, in:Logic and Data Bases, ed. H. Gallaire and J. Minker (Plenum Press, New York, 1978) pp. 77–102.
J. McCarthy, Circumscription — a form of non-monotonic reasoning, Artificial Intelligence 13(1980) 27–39.
W. Marek and V.S. Subrahmanian, The relationship between stable, supported, default and autoepistemic semantics for general logic programs, Theor. Comp. Sci. 10(3)(1992)365–386.
W. Marek and M. Truszczynski, Stable semantics for logic programs and default theories, in:Proc. 1989 North American Conf. on Logic Programming, ed. E. Lusk and R. Overbeek (MIT Press, 1989) pp. 243–256.
T.C. Przymusinski, On the semantics of stratified deductive databases, in:Proc. Workshop on Foundations of Deductive Databases and Logic Programming, ed. J. Minker, Washington, D.C. (1986) pp. 433–443.
T.C. Przymusinki, Extended stable semantics for normal and disjunctive programs, in:Proc. 7th Int. Conf. on Logic Programming, Jerusalem, 1990 (MIT Press), Extended Abstracts, pp. 459–477.
T.C. Przymusinski, Stable semantics for disjunctive programs, New Generation Comput. J. 9(1991) 401–424. Extended Abstract appeared in [14].
R. Reiter, Towards a logical reconstruction of relational database theory, in:On Conceptual Modelling, ed. M.L. Brodie et al. (Springer, New York, 1984) pp. 163–189.
R. Reiter, What should a database know? in:Proc. 7th Int. Conf. on Logic Programming, Jerusalem (1990), Abstract of Invited Talk, p. 765.
M.H. van Emden and R.A. Kowalski, The semantics of predicate logic as a programming language, J. ACM 23(1976)733–742.
D.S. Warren, Using OLDT evaluation with meta-interpreters, in:Logic in Databases, Knowledge, Representation and Reasoning: A Symposium in Honor of Jack Minker's 65th Birthday for Contributions to Computer Science and Human Rights, College Park, Maryland (Nov. 1992).
A. Yahya and L.J. Henschen, Deduction in non-Horn databases, J. Aut. Reasoning 1(1985)141–160.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Fernández, J.A., Lobo, J., Minker, J. et al. Disjunctive LP+integrity constraints= stable model semantics. Ann Math Artif Intell 8, 449–474 (1993). https://doi.org/10.1007/BF01530802
Issue Date:
DOI: https://doi.org/10.1007/BF01530802