On Extended Disjunctive Logic Programs
 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
This paper studies, in a comprehensive manner, different aspects of
extended disjunctive logic programs, that is, programs whose clauses
are of the form
l1 or ... or lk < lk+1,...,lm,not lm+1,...,not ln
where l1,...,ln are literals (i.e. atoms and classically negated
atoms), and not is the negationbydefault operator. The explicit use
of classical negation suggests the introduction of a new truth value,
namely, logical falsehood (in contrast to falsehoodbydefault) in the
semantics. General techniques are described for extending the model,
fixpoint, and proof theories 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 se mantics. Also, the
declarative complexity of the extended programs as well as the
algorithmic complexity of the proof procedures are discussed.
Bibliography

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

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

3. 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.

4. 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.

5. 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.

6. M. Cadoni and M. Schaerf.
A survey on complexity results for nonmonotonic logics.
Preprint, Universit`a di Roma "La Sapienza",
via Salaria 113, 00198 Roma, Italy, 1992.

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

8. J. A. Fernandez and J. Lobo.
A proof procedure for stable theories.
Technical Report CSTR3034, UMIACSTR9314,
Department of Computer Science.
University of Maryland,
College Park, MD. 20742 USA,
1993.

9. J. A. Fernandez,
J. Lobo,
J. Minker, and
V.S. Subrahmanian.
Disjunctive lp + integrity constraints = stable model semantics.
Annals of Mathematics and Artificial Inteligence, 8(34), 1993.

10. M. Gelfond.
On stratified autoepistemic theories.
In Proceedings of AAAI87, pages 207211, 1987.

11. M. Gelfond and V. Lifschitz.
The stable model semantics for logic programming.
In R. Kowalski and K. Bowen, editors,
Procedings of the Fifth International Conference and Symposium on
Logic Programming, pages 10701080, Seattle, WA.
USA, Aug. 1988. The MIT Press.

12. M. Gelfond and V. Lifschitz.
Logic programs with classical negation.
In D.H.D. Warren and P. Szeredi, editors,
Proceedings of the Seventh International Conference on
Logic Programming,
pages 579597, Jerusalem, Israel, June 1990. The MIT Press.

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

14. 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.

15. J.W. Lloyd.
Foundations of Logic Programming.
SpringerVerlag, second extended edition, 1987.

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

17. 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 Programming,
pages 446460, Washington, USA, Nov 1992. The MIT Press.

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

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

20. J. Minker.
On indefinite databases and the closed world assumption.
In Proceedings of the Sixth Conference on Automated Deduction,
pages 292308, 1982.

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

22. P. Pearce and G. Wagner.
Logic programming with strong negation.
In P. SchroederHeister, editor,
Proceedings of the International Workshop on Extensions of
Logic Programming,
pages 311326, T"ubingen, FRG, Dec. 1989.
Lecture Notes in Artificial Intelligence, Springer Verlag.

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

24. 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.

25. T.C. Przymusinski.
Extended stable semantics for normal and disjunctive programs.
In D.H.D. Warren and P. Szeredi, editors,
Proceedings of the Seventh International Conference on Logic Programming,
pages 459477, Jerusalem, Israel, June 1990. The MIT Press.

26. T.C. Przymusinski.
Stationary semantics for disjunctive logic programs and
deductive databases.
In S. Debray and M. Hermenegildo, editors,
Proceedings of the North American Conference on Logic Programming,
pages 4259, Austin, TX. USA, Oct. 1990. The MIT Press.

27. A. Rajasekar, J. Lobo, and J. Minker.
Weak generalized closed world assumption.
Automated Reasoning, 5:293307, 1989.

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

29. K.A. Ross and R.W. Topor.
Inferring negative information from disjunctive databases.
Journal of Automated Reasoning, 4(2):397424, Dec. 1988.

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

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

32. 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.

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