Semantics for Disjunctive Logic Programs with Explicit and Default Negation

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 negation-by-default, 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 well-founded 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 89-148. 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 574-588, 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 well-founded semantics for logic programs. In Proceedings of the Tenth International Con- ference on Automated Deduction, pages 102-116, Germany, 1989. Springer Verlag.
[BLM90a] C. Baral, J. Lobo, and J. Minker. Generalized disjunctive well-founded semantics: Declarative semantics. In Proceedings of the Fifth International Symposium on Methodologies for Intelligent Systems, pages 465-473, Knoxville TN, USA, 1990.
[BLM90b] C. Baral, J. Lobo, and J. Minker. Generalized disjunctive well-founded semantics: Procedural semantics. In Proceedings of the Fifth International Symposium on Methodologies for Intelligent Systems, pages 456-464, 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 459-468, Charlotte NC, USA, 1991.
[CH85] A. Chandra and D. Harel. Structure and complexity of relational queries. Journal of Logic Programming, 2(1):1-15, 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 111-125, 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 293-322. 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 CS-TR-3034, UMIACS-TR-93-14, 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(3-4), 1993.
[Gel87] M. Gelfond. On stratified autoepistemic theories. In Proceedings of AAAI-87, pages 207-211, 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 1070-1080, 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:365-385, 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 400-415, Saratoga Springs NY, USA, June 1992. Springer-Verlag.
[Llo87] J.W. Lloyd. Foundations of Logic Programming. Springer-Verlag, 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 255-267, 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 292-308, 1982. Also in: Lecture Notes in Computer Sci- ence 138, pages 292-308. 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 446-460, Washington D.C., USA, Nov 1992. The MIT Press.
[MR88] J. Minker and A. Rajasekar. Procedural interpretation of non-Horn logic programs. In E.L. Lusk and R.A. Overbeek, editors, Proceedings of the Ninth International Conference on Automated Deduction, pages 278-293, 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 381-394, 1989. (Invited Lecture).
[MR90] J. Minker and A. Rajasekar. A fixpoint semantics for disjunctive logic programs. Journal of Logic Programming, 9(1):45-74, 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 1-18. Lecture Notes in AI. Springer-Verlag, June 1993. (Invited Paper).
[MT91a] V. W. Marek and Truszczy'nski. Autoepistemic logic. Journal of the ACM, 38(3):588-619, 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 Non-monotonic Reasoning, pages 37-50. The MIT Press, 1991.
[MZ82] J. Minker and G. Zanon. An extension to linear resolution with selection function. Information Processing Letters, 14(3):191-194, 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 193-216. 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 1081-1096, 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 SIGACT-SIGMOD-SIGART Symposium on Principle of Database Systems, pages 11-21, 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 459-477, 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 42-59, Austin, TX. USA, Oct. 1990. The MIT Press.
[Prz91] T. C. Przymusinski. Stable semantics for disjunctive programs. New Generation Computing, 9:401-424, 1991.
[PW89] P. Pearce and G. Wagner. Logic programming with strong nega- tion. In P. Schroeder-Heister, 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 55-76. Plenum, New York, 1978.
[RLM89] A. Rajasekar, J. Lobo, and J. Minker. Weak generalized closed world assumption. Journal of Automated Reasoning, 5:293-307, 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, CS-1991-11. Dept. of Com- puter Science. Duke University.
[Ros89a] K.A. Ross. A procedural semantics for well-founded negation in logic programs. In Proceedings of the Eighth ACM SIGACT-SIGMOD- SIGART Symposium on Principle of Database Systems, Philadel- phia, PA. USA, 1989.
[Ros89b] K.A. Ross. Well-founded semantics for disjunctive logic programs. In Proceedings of the First International Conference on Deductive and Object Oriented Databases, pages 352-369, 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 Recursion-theoretic Methods in Logic Programming., pages 143-164, Washington, D.C. USA, Nov. 1992.
[Sho67] J. Shoenfield. Mathematical Logic. Addison-Wesley, 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 1149-1176. Morgan Kaufmann, 1988.
[VGRS88] A. Van Gelder, K.A. Ross, and J.S. Schlipf. Unfounded sets and well-founded semantics for general logic programs. In Proceedings of the Seventh ACM Symposium on Principles of Database Systems., pages 221-230, 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 1-15, Rostock,Germany, May 1991. Lecture Notes in Computer Science, Springer -Verlag.
[YH85] A. Yahya and L.J. Henschen. Deduction in non-Horn databases. Journal of Automated Reasoning, 1(2):141-160, 1985.