Mixing a Default Rule with Stable Negation

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

The complete paper is available in:

Abstract

Logic programs containing only at most one form of default negation have been studied in the literature. We describe a class of logic programs containing multiple forms of default negation. We define a meaning for these programs based on the well--founded semantics and the stable semantics. We investigate properties of the new combined semantics and calculate the computational complexity of determining the existence of models, and of skeptical and credulous reasoning. An effective procedure to construct the collection of models characterizing the semantics of a program is given. Applications to knowledge representation and knowledge base merging are presented.

Bibliography

[GL88] Gelfond, M., and Lifschitz, V. The stable model semantics for logic programming. In Kowalski, and Bowen, eds., Proc. of the Fifth Intl. Conf. and Symp. on Logic Programming, 1070--1080. The MIT Press. 1988.
[Prz91] Przymusinski, T.C. Stable semantics for disjunctive programs. New Gen. Comp. 9:401--424. 1991.
[RM95] C. Ruiz and J. Minker. Computing stable and partial stable models of extended disjunctive logic programs. In Dix, Pereira, and Przymusinski, eds., Nonmonotonic Extensions of Logic Programming. LNCS 927. Springer-Verlag, 205--229. 1995.
[Sch92] Schlipf, J. A survey of complexity and undecidability results in logic programming. In Blair, Marek, Nerode, and Remmel, eds., Informal Proc. of the Worshop on Structural Complexity and Recursion-theoretic Methods in Logic Programming., 143--164. 1992.
[VRS88] Van Gelder, A.; Ross, K.; and Schlipf, J. Unfounded sets and well-founded semantics for general logic programs. In Proc. of the Seventh ACM Symp. on Principles of Database Systems., 221--230. 1988.