Semantics for Disjunctive Logic Programs with Explicit and Default
Negation
 Department of Computer Science
 Institute for Advanced Computer Studies
 University of Maryland,
College Park, MD 20742, USA.
 Jack Minker
 Carolina Ruiz
The complete paper is available in:
Abstract
The use of explicit negation enhances the expressive power of logic programs
by providing a natural and unambiguous way to assert negated information about
the domain being represented. We study the semantics of disjunctive programs
that contain both explicit negation and negationbydefault, called extended
disjunctive logic programs. General techniques
are described for extending model, fixpoint, and proof theoretic
characterizations of an arbitrary semantics of normal
disjunctive logic programs to cover the class of extended programs.
Illustrations of these techniques are given for stable models, disjunctive
wellfounded and stationary semantics. The declarative complexity of the
extended programs, as well as the algorithmic complexity of the proof
procedures and fixpoint operators, are discussed.
Bibliography

[ABW88] K.R. Apt, H.A. Blair, and A. Walker. Towards a theory of declar
ative knowledge. In J. Minker, editor,
Foundations of Deductive Databases and Logic Programming,
pages 89148. Morgan Kaufmann Pub., Washington, D.C. USA, 1988.

[AP92] J.J. Alferes and L.M. Pereira. On logic program semantics with two
kinds of negation. In K. Apt, editor, Proceedings of the Joint Inter
national Conference and Symposium on Logic Programming, pages
574588, Washington, D.C. USA, Nov 1992. The MIT Press.

[Bar91] C. Baral. Issues in Knowledge Representation: Semantics and
Knowledge Combination. PhD thesis, Dept. of Computer Science
University of Maryland, College Park, MD. 20742 USA, 1991.

[Bel88] N. Belegrinos. Clauses, Partial Interpretations and the Closed World
Assumption. PhD thesis, Dept. Of Computer Science. University of
Melbourne, Parkville, Victoria. Australia, 1988.

[BLM89] C. Baral, J. Lobo, and J. Minker.
Generalized wellfounded semantics for logic programs.
In Proceedings of the Tenth International Con
ference on Automated Deduction, pages 102116, Germany, 1989.
Springer Verlag.

[BLM90a] C. Baral, J. Lobo, and J. Minker.
Generalized disjunctive wellfounded semantics: Declarative semantics.
In Proceedings of the Fifth International Symposium on
Methodologies for Intelligent Systems,
pages 465473, Knoxville TN, USA, 1990.

[BLM90b] C. Baral, J. Lobo, and J. Minker.
Generalized disjunctive wellfounded semantics: Procedural semantics.
In Proceedings of the Fifth International Symposium on
Methodologies for Intelligent Systems,
pages 456464, Knoxville TN, USA, 1990.

[BLM91] C. Baral, J. Lobo, and J. Minker.
WF3: A semantics for negation in normal disjunctive logic programs.
In Proceedings of the Sixth International Symposium on
Methodologies for Intelligent Systems,
pages 459468, Charlotte NC, USA, 1991.

[CH85] A. Chandra and D. Harel. Structure and complexity of relational
queries. Journal of Logic Programming, 2(1):115, April 1985.

[Cha88] D. Chan. Constructive negation based on the completed database.
In R. Kowalski and K. Bowen, editors, Proceedings of the Fifth Inter
national Conference and Symposium on Logic Programming, pages
111125, Seattle, WA. USA, Aug. 1988. The MIT Press.

[Cla78] K.L. Clark. Negation as failure.
In H. Gallaire and J. Minker, editors,
Logic and Data Bases, pages 293322. Plenum, New York, USA,
1978.

[CS92] M. Cadoli and M. Schaerf. A survey on complexity results for non
monotonic logics. Preprint, Universit`a di Roma "La Sapienza", via
Salaria 113, 00198 Roma, Italy. To appear in the Journal of Logic
Programming, special issue edited by T. Przymusinski on Logic Pro
gramming and Nonmonotonic Reasoning, 1992.

[FL93] J.A. Fern'andez and J. Lobo.
A proof procedure for stable theories.
Technical Report CSTR3034, UMIACSTR9314,
University
of Maryland, College Park, MD 20742 USA, 1993.

[FLMS93] J.A. Fern'andez, J. Lobo, J. Minker, and V.S. Subrahmanian.
Disjunctive lp + integrity constrains = stable model semantics.
Annals of Mathematics and Artificial Intelligence, 8(34), 1993.

[Gel87] M. Gelfond. On stratified autoepistemic theories. In Proceedings of
AAAI87, pages 207211, 1987.

[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 Pro
gramming, pages 10701080, Seattle, WA. USA, Aug. 1988. The MIT
Press.

[GL90] M. Gelfond and V. Lifschitz. Logic programs with classical nega
tion. In D.H.D. Warren and P. Szeredi, editors, Proceedings of the
Seventh International Conference on Logic Programming, pages 579
597, Jerusalem, Israel, June 1990. The MIT Press.

[GL91] M. Gelfond and V. Lifschitz. Classical negation in logic programs
and disjunctive databases. New Generation Computing, 9:365385,
1991.

[Hil74] R. Hill. Lush resolution and its completeness. Technical Report
DCL Memo 78, Department of Artificial Intelligence, University of
Edinburgh, August 1974.

[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 400415, Saratoga Springs NY, USA, June 1992.
SpringerVerlag.

[Llo87] J.W. Lloyd. Foundations of Logic Programming. SpringerVerlag,
second extended edition, 1987.

[LMR89] J. Lobo, J. Minker, and A. Rajasekar.
Extending the semantics of logic programs to disjunctive
logic programs. In G. Levi and
M. Martelli, editors, Proceedings of the Sixth International Con
ference on Logic Programming, pages 255267, Cambridge, Mas
sachusetts., June 1989. MIT Press.

[LMR92] J. Lobo, J. Minker, and A. Rajasekar.
Foundations of Disjunctive Logic Programming. The MIT Press, 1992.

[Lob91] J. Lobo. Semantics for Normal Disjunctive Logic Programs. PhD thesis,
Dept. of Computer Science. Univ. of Maryland.,
College Park,
MD 20742. USA, 1991.

[Min82] J. Minker.
On indefinite databases and the closed world assumption.
In Proceedings of the Sixth Conference on Automated Deduction,
pages 292308, 1982. Also in: Lecture Notes in Computer Sci
ence 138, pages 292308. Springer Verlag, 1982.

[MNR92] V. W. Marek, A. Nerode, and J.B. Remmel. The stable models
of a predicate logic program. In K. Apt, editor, Proceedings of the
Joint International Conference and Symposium on Logic Program
ming, pages 446460, Washington D.C., USA, Nov 1992. The MIT
Press.

[MR88] J. Minker and A. Rajasekar.
Procedural interpretation of nonHorn logic programs.
In E.L. Lusk and R.A. Overbeek, editors,
Proceedings of the Ninth International Conference on
Automated Deduction, pages 278293, Argonne, IL. USA, May 1988.

[MR89] J. Minker and A. Rajasekar.
Disjunctive logic programming.
In Proceedings of the International Symposium on Methodologies for
Intelligent Systems, pages 381394, 1989. (Invited Lecture).

[MR90] J. Minker and A. Rajasekar.
A fixpoint semantics for disjunctive logic programs.
Journal of Logic Programming, 9(1):4574, July 1990.

[MR93] J. Minker and
C. Ruiz.
On extended disjunctive logic programs.
In J. Komorowski and Z.W. Ra's, editors, Proceedings of the Seventh
International Symposium on Methodologies for Intelligent Systems,
pages 118. Lecture Notes in AI. SpringerVerlag, June 1993. (Invited
Paper).

[MT91a] V. W. Marek and Truszczy'nski. Autoepistemic logic. Journal of the
ACM, 38(3):588619, 1991.

[MT91b] V. W. Marek and Truszczy'nski. Computing intersection of autoepis
temic expansions. In Proceedings of the Fifth International Workshop
on Logic Programming and Nonmonotonic Reasoning, pages 3750.
The MIT Press, 1991.

[MZ82] J. Minker and G. Zanon.
An extension to linear resolution with selection function.
Information Processing Letters, 14(3):191194, June 1982.

[Nel49] D. Nelson. Constructive falsity. Journal of Symbolic Logic, 14(1):16
26, March 1949.

[Prz88a] T.C. Przymusinski. On the declarative semantics of deductive
databases and logic programming.
In J. Minker, editor,
Foundations of Deductive Databases and Logic Programming,
pages 193216. Morgan Kaufmann, 1988.

[Prz88b] T.C. Przymusinski. Perfect model semantics. In R. Kowalski and
K. Bowen, editors, Proceedings of the Fifth International Conference
and Symposium on Logic Programming, pages 10811096, Seattle,
WA. USA, Aug. 1988. The MIT Press.

[Prz89a] T.C. Przymusinski. Every logic program has a natural stratification
and an iterated fixed point model. In Proceedings of the Eighth ACM
SIGACTSIGMODSIGART Symposium on Principle of Database
Systems, pages 1121, Philadelphia, PA. USA, 1989.

[Prz89b] T.C. Przymusinski. On the declarative and procedural semantics of
logic programs. Journal of of Automated Reasoning, 5(2), June 1989.

[Prz90a] T.C. Przymusinski. Extended stable semantics for normal and dis
junctive programs. In D.H.D. Warren and P. Szeredi, editors, Pro
ceedings of the Seventh International Conference on Logic Program
ming, pages 459477, Jerusalem, Israel, June 1990. The MIT Press.

[Prz90b] T.C. Przymusinski. Stationary semantics for disjunctive logic pro
grams and deductive databases. In S. Debray and M. Hermenegildo,
editors, Proceedings of the North American Conference on Logic Pro
gramming, pages 4259, Austin, TX. USA, Oct. 1990. The MIT
Press.

[Prz91] T. C. Przymusinski. Stable semantics for disjunctive programs. New
Generation Computing, 9:401424, 1991.

[PW89] P. Pearce and G. Wagner. Logic programming with strong nega
tion. In P. SchroederHeister, editor, Proceedings of the Interna
tional Workshop on Extensions of Logic Programming, pages 311
326, T"ubingen, FRG, Dec. 1989. Lecture Notes in Artificial Intelli
gence, Springer Verlag.

[Rei78] R. Reiter. On closed world data bases.
In H. Gallaire and J. Minker, editors,
Logic and Data Bases, pages 5576. Plenum, New York, 1978.

[RLM89] A. Rajasekar, J. Lobo, and J. Minker.
Weak generalized closed world assumption.
Journal of Automated Reasoning, 5:293307, 1989.

[RLS91] D.W. Reed, D.W. Loveland, and B.T. Smith. An alternative charac
terization of disjunctive logic programs. In Proceedings of the Inter
national Logic Programming Symposium, Cambridge, Massachusetts,
1991. MIT Press. Also: Technical Report, CS199111. Dept. of Com
puter Science. Duke University.

[Ros89a] K.A. Ross. A procedural semantics for wellfounded negation in logic
programs. In Proceedings of the Eighth ACM SIGACTSIGMOD
SIGART Symposium on Principle of Database Systems, Philadel
phia, PA. USA, 1989.

[Ros89b] K.A. Ross. Wellfounded semantics for disjunctive logic programs.
In Proceedings of the First International Conference on Deductive
and Object Oriented Databases, pages 352369, Kyoto, Japan, 1989.

[RT88] K. A. Ross and R. W. Topor. Inferring negative information from
disjunctive databases. Journal of Automated Reasoning, 4(2):397
424, December 1988.

[Sch92] J.S. Schlipf. A survey of complexity and undecidability results in
logic programming. In H. Blair, V.W. Marek, A. Nerode, and J. Rem
mel, editors, Informal Proceedings of the Worshop on Structural
Complexity and Recursiontheoretic Methods in Logic Programming.,
pages 143164, Washington, D.C. USA, Nov. 1992.

[Sho67] J. Shoenfield. Mathematical Logic. AddisonWesley, 1967.

[vEK76] M.H. van Emden and R.A. Kowalski. The semantics of predicate
logic as a programming language. Journal of the ACM, 23(4):733
742, 1976.

[VG88] A. Van Gelder. Negation as failure using tight derivations for gen
eral logic programs.
In J. Minker, editor,
Foundations of Deductive Databases and Logic Programming,
pages 11491176. Morgan Kaufmann, 1988.

[VGRS88] A. Van Gelder, K.A. Ross, and J.S. Schlipf. Unfounded sets and
wellfounded semantics for general logic programs. In Proceedings of
the Seventh ACM Symposium on Principles of Database Systems.,
pages 221230, 1988.

[Wag91] G. Wagner. A database needs two kinds of negation. In B. Thal
heim, J. Demetrovics, and H.D. Gerhardt, editors, Proceedings of
the Third Symposium on Mathematical Fundamentals of Database
and Knowledge Base Systems, pages 115, Rostock,Germany, May
1991. Lecture Notes in Computer Science, Springer Verlag.

[YH85] A. Yahya and L.J. Henschen. Deduction in nonHorn databases.
Journal of Automated Reasoning, 1(2):141160, 1985.