An Overview of Nonmonotonic Reasoning and Logic Programming

Journal of Logic Programming, Vol. 17, No. 2, 3, \& 4, 95-126, Nov. 1993

Jack Minker

Department of Computer Science and

Institute for Advanced Computer Studies

University of Maryland, College Park, MD 20742

The complete paper is available in:

PostScript

available.

Abstract

The focus of this paper is nonmonotonic reasoning as it relates to logic programming. I discuss the pre-history of nonmonotonic reasoning starting from approximately 1958. I then review the research that has been accomplished in the areas of circumscription, default theory, modal theories and logic programming. The overview includes the major results developed including complexity results that are known about the various theories. I then provide a summary which includes an assessment of the field and what must be done to further research in nonmonotonic reasoning and logic programming.

Bibliography

[AB88] K.R. Apt and H.A. Blair. Arithmetic classification of perfect models of stratified programs. R.A. Conference and Symposium on Logic Programming, pages 766-779, 1988.
[AB90] K.R. Apt and M. Bezem Acyclic programs. Logic Programming: Proceedings of the Seventh International Conference, D.H.D. Warren an P. Szeredi, eds. MIT Press, 617-633, 1990.
[ABW88] K.R. Apt, H.A. Blair, and A. Walker. Towards a theory of declarative knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 89-148. Morgan Kaufmann Pub., Washington, D.C., 1988.
[AP92] J.J. Alferes and L.M. Pereira. On logic program semantics with two kinds of negation. In Proceedings of the Joint International Conference and Symposium on Logic Programming, pages 574-588, 1992.
[BE89] A. Borgida and D.W. Etherington. Hierarchical knowledge bases and efficient disjunction. In Proceedings of the First International Conference on Principle of Knowledge Represen- tation and Reasoning (KR-89), pages 33-43, Toronto, Ontario, Canada, 1989.
[BF88] N. Bidoit and C. Froidevaux. General logical databases and programs: Default logic semantics and stratification. Journal of Information and Computation, v.91, no.1, 15-54, March, 1991.
[BH86] N. Bidoit and R. Hull. Positivism vs. minimalism in deductive databases. Proc. ACM SIGACT-SIGMOD Symposium on the Principles of Database Systems, pages 123-132, 1986.
[BKMS91] C. Baral, S. Kraus, J. Minker, and V.S. Subrahmanian. Combining knowledge bases consisting of first order theories. Computational Intelligence , 8(1), 45-71, March 1992.
[BLM90a] C. Baral, J. Lobo, and J. Minker. Generalized disjunctive well-founded semantics for logic programs: Declarative semantics. In Proc. of Fifth International Symposium on Methodologies for Intelligent Systems, 465-473, Knoxville, TN, 1990.
[BLM90b] C. Baral, J. Lobo, and J. Minker. Generalized disjunctive well-founded semantics for logic programs: Procedural semantics. In Proc. of Fifth International Symposium on Methodologies for Intelligent Systems, 456-464, Knoxville, TN, 1990.
[BLM90c] C. Baral, J. Lobo, and J. Minker. Generalized well-founded semantics for logic programs. In M. E. Stickel, editor, Proc. of Tenth International Conference on Automated Deduction, pages 102-116, Kaiserslautern, FRG, July, 1990. Springer-Verlag.
[BLM91] C. Baral, J. Lobo, and J. Minker. WF3: A semantics for negation in normal disjunctive logic programs. In Proc. of sixth International Symposium on Methodologies for Intelligent Systems, 459-468, Charlotte, NC, 1991.
[BNNS91] C. Bell, A. Nerode, R. Ng, and V.S. Subrahmanian. Computation and implementation of non-monotonic deductive databases. Technical report, Dept. of Computer Science, University of Maryland at College Park, 1991.
[BR92] L. Bertossi and R. Reiter. Circumscription and Generic Mathematical Objects. Technical Report, University of Toronto, 1992.
[BS85] G. Bossu and P. Siegel. Saturation, nonmonotonic reasoning and the closed-world assump- tion. Artificial Intelligence, 25(1):13-63, 1985 January 1985.
[BS89] H. Blair and V.S. Subrahmanian. Paraconsistent Logic Programming. Theoretical Com- puter Science, 68:135-154, 1989.
[BS91] C. Baral and V. S. Subrahmanian. Dualities between alternative semantics of logic pro- grams and nonmonotonic formalisms. In A. Nerode, W. Marek, and V.S. Subrahmanian, editors, Logic Programming and Non-monotonic Reasoning: Proceedings of the First In- ternational Workshop, pages 69-86. MIT Press, 1991.
[BS92] C. Baral and V.S. Subrahmanian. Stable and extension class theory for logic programs and default logics. Journal of Automated Reasoning, 8:345-366, 1992.
[Bar91] C. Baral. Issues in Knowledge Representation: Semantics and Knowledge Combination. PhD thesis, University of Maryland, College Park, Maryland 20742, 1991.
[Bar92] C. Baral. Generalized negation as failure and semantics of normal disjunctive logic pro- grams. In International Conference on Logic Programming and Automated Reasoning: Lecture Notes in AI 624, Springer Verlag, pages 309-319, 1992.
[Bel77a] N. Belnap. How a computer should think. In G. Ryle, editor, Contemporary Aspects of Philosophy, pages 30-56. Oriel Press, 1977.
[Bel77b] N. Belnap. A useful four-valued logic. In J.M. Dunn and G. Epstein, editors, Modern Uses of Multiple-valued Logic, pages 8-37. D. Reidel, 1977.
[Bid91] N. Bidoit. Negation in rule-based database languages: a survey. Theoretical Computer Science, 78, 3-83, 1991.
[Bon92] P.A. Bonatti. Autoepistemic logics as a unifying framework for the semantics of logic programs. In Proceedings of the Joint International Conference and Symposium on Logic Programming, pages 417-430, 1992.
[Bre89] Ph. Bresnard. An Introduction to Default Logic. Springer-Verlag, 1989.
[Bre91] G. Brewka. Nonmonotonic Reasoning: Logical Foundations of Common Sense. Cambridge University Press, Cambridge, 1991.
[CH82] A. Chandra and D. Harel. Structure and complexity of relational queries. Journal of Computer System Sciences, 25:99-128, 1982.
[CKPR73] A. Colmerauer, H. Kanoui, R. Pasero, and P. Roussel. Un systeme de communication homme-machine en francais. Technical report, Groupe de Intelligence Artificielle Univer- sitae de Aix-Marseille II, Marseille, 1973.
[CL90] M. Cadoli and M. Lenzerini. The complexity of closed world reasoning and circumscription. Proceedings of the AAAI, pages 550-555, 1990 Also Technical report, Universita di Roma "La Sapienza", Dipartimento di Informatica e Sistemistica, Roma, Italy, 1990.
[CS89] J. Chomicki and V.S. Subrahmanian. Generalized closed world assumption is ss02 com- plete. Technical Report TR-89-036, Computer Science Department, University of North Carolina, 1989. Information Processing Letters., 34:289-291, 1990.
[CS92] M. Cadoli and M. Schaerf. A survey on complexity results for non-monotonic logics. Technical report, Universita di Roma "La Sapienza", Dipartiment o di Informatica e Sis- temistica, Roma, Italy, 1992.
[CW92] W. Chen and D.S. Warren. A goal oriented approach to computing well founded se- mantics. In Proceedings of the Joint International Conference and Symposium on Logic Programming, pages 589-606, 1992.
[Cha88] D. Chan. Constructive negation based on the completed databases. In R.A. Kowalski and K.A. Bowen, editors, Proc. 5th International Conference and Symposium on Logic Programming, pages 111-125, Seattle, Washington, August 15-19, 1988.
[Cla78] K.L. Clark. Negation as failure. In Logic and Databases, eds. H. Gallaire and J. Minker, 293-322, Plenum, New York, 1978.
[DD92] M. Denecker and D. De Schreye. Sldnfa: an abductive procedure for normal abductive programs. In Proceedings of the Joint International Conference and Symposium on Logic Programming, pages 686-702, 1992.
[DLNPS90] F.M. Donini, M. Lenzerini, D. Nardi, F. Pirri, M. Schaerf Nonmonotonic reasoning Artificial Intelligence Review, vol. 4, 163-210, 1990.
[DeK86] J. de Kleer. An assumption-based TMS. Artificial Intelligence, 32, 1986.
[Del88] J. Delgrande. An approach to default reasoning based on a first-order conditional logic: revised report. Artificial Intelligence, 36:63-90, 1988.
[Dem68] A.P. Dempster. A Generalization of Bayesian Inference. J. of the Royal Statistical Society, Series B, 30, 205-247, 1968.
[Dix91] J. Dix. Classifying semantics of logic programs. In A. Nerode, W. Marek, and V.S. Subrahmanian, editors, Logic Programming and Non-monotonic Reasoning: Proceedings of the First International Workshop, pages 166-180. MIT Press, 1991.
[Dix92] J. Dix. Classifying semantics of disjunctive logic program. In Proceedings of the Joint International Conference and Symposium on Logic Programming, pages 798-812, 1992.
[Doy79] J. Doyle. A truth maintenance system. Artificial Intelligence, 12:231-272, l979.
[Doy82] J. Doyle. Some theories of reasoned assumptions: An essay in rational psychology. Tech- nical Report, Department of Computer Science, Carnegie-Mellon University, 1982.
[Doy83] J. Doyle. The ins and outs of reason maintenance. In Proceedings of Eighth IJCAI, pp. 349-351, 1983.
[Dung92] P.M. Dung. On the relations between stable and well-founded semantics of logic programs. Theoretical Computer Science: Logic, semantics and theory of programming, 105:7-26, 1992.
[EDP90] J. Elgot-Drapkin and D. Perlis. Reasoning situated in time i: basic concepts. J. of Experimental and Theoretical Artificial Intelligence, 2:75-98, 1990.
[EK76] M.H. van Emden and R.A. Kowalski The semantics of predicate logic as a programming language Journal of the ACM, 23(4), pp. 733-742, 1976.
[EK88] K. Eshghi and R.A. Kowalski. Abduction through deduction. Technical Report, Dept. of Computing, Imperial College, London, 1988.
[EK89] K. Eshghi and R.A. Kowalski. Abduction compared with negation by failure. In Proc. 6th International Conference on Logic Programming, 234-255, Lisbon, 1989.
[EKP91] D. Etherington, S. Kraus, and D. Perlis. Nonmonotonicity and the scope of reasoning. Artificial Intelligence, 52:221-261, 1991.
[EMR85] D. Etherington, R. Mercer, and R. Reiter. On the adequacy of predicate circumscription for closed world reasoning. Computational Intelligence 1, pages 11-15, 1985.
[ER83] D.W. Etherington and R. Reiter. On inheritance hierarchies with exceptions. In Pro- ceedings of American Association for Artificial Intelligence at National Conference, pages 104-108, 1983.
[Esh88] K. Eshghi. Abductive planning with event calculus. In Proc. 5th International Conference and Symposium on Logic Programming, 562-579, Seattle, Washington, 1988.
[Esh90] K. Eshghi. Diagnoses as stable models. In Proc. 1st International Workshop on Principles of Diagnoses, Menlo Park, CA, 1990.
[Eva89] C. Evans Negation-as-failure as an approach to the Hanks and McDermott problem. Proceedings of the Second International Conference on Artificial Intelligence, 1969.
[FLM91] M. Freund, D. Lehmann and P. Morris. Rationality, transitivity and contraposition. Ar- tificial Intelligence, 52, 191-203, 1991.
[FLMS93] J.A. Fernandez, J. Lobo, J. Minker, and V.S. Subrahmanian. Disjunctive LP + integrity constraints = stable model semantics. In Annals of Mathematics and AI 8, No. 3-4 (1993)
[FM91a] J.A. Fernandez and J. Minker. Bottom-up evaluation of hierarchical disjunctive deductive databases. In Proc. International Conference on Logic Programming, 660-675, Paris, 1991. MIT Press.
[FM91b] J.A. Fernandez and J. Minker. Computing perfect models of disjunctive stratified databases. In Proc. ILPS '91 Workshop on Disjunctive Logic Programs, 110-117, eds. D. Loveland, J. Lobo, and A. Rajasekar, San Diego, CA, Oct. 1991.
[FM92a] J.A. Fernandez and J. Minker. Semantics of disjunctive deductive databases. In Interna- tional Conference on Database Theory: Lecture Notes in Computer Science 646, Springer Verlag, pages 21-50, 1992.
[FM92b] J.A. Fernandez and J. Minker. Disjunctive deductive databases. In International Confer- ence on Logic Programming and Automated Reasoning: Lecture Notes in AI 624, Springer Verlag, pages 332-356, 1992.
[FM93] J.A. Alberto Fern'andez and J. Minker. Theory and algorithms for disjunctive deductive databases. Programmirovanie Journal, 1993. Invited Paper by the Academy of Sciences of Russia (To appear).
[Fah79] S.E. Fahlman. Netl: A System for Representing and Using Real-World Knowledge. M.I.T. Press, 1979.
[Fit85] M. Fitting. A Kripke-Kleene semantics for logic programs. Journal of Logic Programming, 2(4):295-312, 1985.
[Fit91] M.C. Fitting. Well-founded semantics, generalized. In International Symposium on Logic Programming, pages 71-84, 1991.
[GL88] M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Proceedings of the 5th Logic Programming Symposium, pages 1070-1080, Association for Logic Programming, MIT Press, Cambridge, Mass, 1988.
[GL90] M. Gelfond and V. Lifschitz Logic programs with classical negation. Logic Programming: Proceedings of the Seventh International Conference, D.H.D. Warren and P. Szeredi, eds., 579-597, 1990.
[GL91] M. Gelfond and V. Lifschitz. Classical negation in logic programming and disjunctive databases. New Generation Computing, 9:365-385, 1991.
[GL92] M. Gelfond and V. Lifschitz. Representing actions in extended logic programming. In Proceedings of the Joint International Conference and Symposium on Logic Programming, pages 559-573, 1992.
[GLPT91] M. Gelfond, V. Lifschitz, H. Przymusi'nska, and M. Truszczy'nski. Disjunctive defaults. In J. Allen, R. Fikes, and E. Sandewall, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Second International Conference, pages 230-237, San Mateo, California, April 22-25 1991. Morgan Kaufman.
[GM78] H. Gallaire and J. Minker, editors. Logic and Databases. Plenum Press, New York, April 1978.
[GPP86] M. Gelfond, H. Przymusinska, and T.C. Przymusinski. The extended closed world as- sumption and its relation to parallel circumscription. Proc. Fifth ACM SIGACT-SIGMOD Symposium on Principle of Database Systems, pages 133-139, 1986.
[GPP89] M. Gelfond, H. Przymusinska, and T.C. Przymusinski. On the relationship between cir- cumscription and negation as failure. Artificial Intelligence., 38(1), 75-94, 1989.
[GS90] J. Grant and V.S. Subrahmanian. Reasoning in inconsistent knowledge bases. to appear in IEEE Trans. Knowledge and Data Engineering.
[Gef89] H. Geffner. Default Reasoning: Causal and Conditional Theories. Ph.D thesis, Computer Science Department, UCLA, 1989.
[Gel87] M. Gelfond. On stratified autoepistemic theories. In Proc. AAAI-87, pages 207-211, 1987.
[Gel92] M. Gelfond. Logic programming and reasoning with incomplete information. Technical report, Dept of Computer Science, University of Texas at El Paso, 1992.
[Gin86] M. Ginsberg. Counterfactuals. Artificial Intelligence, 30:35-79, 1986.
[Gin87A] M. Ginsberg. Readings in Nonmonotonic Reasoning. Morgan Kaufmann, Los Altos, Cal- ifornia, 1987.
[Gin89] M. Ginsberg. A circumscriptive theorem prover. Artificial Intelligence, 39:265-316, 1989.
[Gin91] M. Ginsberg. The MVL theorem proving system. SIGART Bulletin: Special Issue on implemented knowledge representation and reasoning systems, 2(3):57-60, 1991.
[Gir92] F. Gire. Well founded semantics and stable semantics of semi-strict programs. In Interna- tional Conference on Database Theory: Lecture Notes in Computer Science 646, Springer Verlag, pages 261-275, 1992.
[Got91] G. Gottlob. Complexity results for nonmonotonic logics. Technical report, Institut fur Informationssysteme, Technishe Universitat, Wien, 1991.
[Gro91] B. Grosof. Generalizing prioritization. In J. Allen, R. Fikes, and E. Sandewall, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Second Inter- national Conference, pages 289-300, San Mateo, California, April 22-25 1991. Morgan Kaufman.
[HP87] L. Henschen and H. Park. Compiling the GCWA in Indefinite Deductive Databases. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 395-439. Morgan Kaufmann Pub., Washington, D.C., 1988.
[HT92] J. Horty and R. Thomason. Conditionals and artificial intelligence. Fundamenta Infor- matica (forthcoming), 1993.
[HTT90] J. Horty, R. Thomason, and D. Touretzky. A skeptical theory of inheritance in nonmono- tonic semantic networks. Artificial Intelligence, 42:311-348, 1990. abbreviated version appears in Proceedings of AAAI-87, Morgan Kaufmann, 358-363.
[Hay73] P.J. Hayes. Computation and deduction. In Proceedings of the Second Symposium on Math- ematical Foundations of Computer Science, pages 105-118. Czechoslovakia: Czechoslo- vakian Academy of Sciences, 1973.
[Hew69] C.E. Hewitt. PLANNER: A language for proving theorems in robots. First International Joint Conference on Artificial Intelligence, pages 295-301, 1969.
[IKH92] K. Inoue, M. Koshimura, and R. Hasegawa. Embedding negation as failure into a model generation theorem prover. In International Conference on Automated Deduction (CADE- 11), pages 400-415, Saratoga Springs, NY, 1992.
[IOHN92] K. Inoue, Y. Ohta, R. Hasegawa and M. Nakashima. Bottom-Up abduction by model generation. Technical Report TR-816, ICOT, Tokyo, October 1992.
[IOHN92] K. Inoue, Y. Ohta, R. Hasegawa, and M. Nakashima. Hypothetical reasoning systems on the MGTP. Technical Report, ICOT, Tokyo (in Japanese), 1992.
[Imi87] T. Imielinski. Results on translating defaults to circumscription. Artificial Intelligence, 32:131-146, 1987.
[Ino90] K. Inoue. An abductive procedure for the CMS/ATMS. In Proc. European Conference on Artificial Intelligence, ECAI 90 International Workshop on Truth Maintenance, Stockholm, Springer Verlag Lecture Notes in Computer Science, 1990.
[Ino91a] K. Inoue. Hypothetical reasoning in logic programs. Technical Report ICOT 607, Tokyo, 1991.
[Ino91b] K. Inoue. Extended logic programs with default assumptions. In Proc. 8th International Conference on Logic Programming, 490-504, Paris, 1991.
[Jer88] R.E. Jeroslow. Computation-Oriented Reductions of Predicate to Propositional Logic. Decision Support Systems, 4, 183-187, 1988.
[KK89] M. Kifer and T. Krishnaprasad. An evidence based framework for a theory of inheri- tance. In Proceedings of 11th Intl. Joint Conf. on Artificial Intelligence, pages 1093-1098, Morgan-Kaufmann, 1989.
[KKT92] A.C. Kakas, R.A. Kowalski, and F. Toni. Abductive Logic Programming. Technical Report, Dept. of Computing, Imperial College, London, Oct. 1992.
[KLM90] S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence, 14(1):167-207, 1990.
[KM90] A.C. Kakas and P. Mancarella. Database updates through abduction. In Proc. 16th International Conference on Very Large Databases, VLDB 90, Brisbane, Australia, 1990.
[KM91] A.C. Kakas and P. Mancarella. Stable theories for logic programs. In International Sym- posium on Logic Programming, pages 85-100 1991.
[KPH91] S. Kraus, D. Perlis, and J. Horty. Reasoning about ignorance: A note on the bush- gorbachev problem. Fundamenta Informaticae, 15:325-332, 1991.
[KS89] H.A. Kautz and B. Selman. Hard problems for simple default logics. In Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning (KR-89), pages 189-197, Toronto, Ontario, 1989.
[KS90] R. Kowalski and F. Sadri. Logic programs with exceptions. In Proc. 7th International Conference on Logic Programming, Jerusalem, Israel, 598-613, 1990.
[Kon88] K. Konolige. On the relation between default and autoepistemic logic. Artificial Intelli- gence, 35(3):343-382, July 1988.
[Kon90] K. Konolige Errata for: On the relation between default and autoepistemic logic. Artificial Intelligence, 41:115, 1990.
[Kon91] K. Konolige. Quantification in autoepistemic logic. Fundamenta Informaticae, 15:275-300, 1991.
[Kri71] S. Kripke. Semantical considerations on modal logic. In L. Lindsay, editor, Reference and Modality, pages 63-72, London, UK, 1971. Oxford University Press.
[Kun89] K. Kunen. Signed dependencies in logic programs. Journal of Logic Programming, 7, 231-245, 1989.
[LM92] D. Lehmann and M. Magidor. What does a conditional knowledge base entail? Artificial Intelligence, 55(1), 1-60, May 1992.
[LMR92] J. Lobo, J. Minker, and A. Rajasekar. Foundations of Disjunctive Logic Programming. MIT Press, 1992.
[LS89] F. Lin and Y. Shoham. Argument systems: A uniform basis for nonmonotonic reasoning. In Proceedings of 1st Intl. Conference on Principles of Knowledge Representation and Reasoning, pages 245-255, Stanford University, Stanford, CA, 1989.
[LS90] F. Lin and Y. Shoham. Epistemic semantics for fixed-points nonmonotonic logics. In R. Parikh, editor, Theoretical Aspects of Reasoning and Knowledge: Proc. of the Third Conf., pages 111-120, Stanford University, Stanford, CA, 1990.
[LS92] J. Lobo and V.S. Subrahmanian. Relating minimal models and pre-requisite-free normal defaults. Information Processing Letters, 44:129-133, 1992.
[Lev84] H.J. Levesque. Foundations of a functional approach to knowledge representation. Artifi- cial Intelligence, 23(2):155-212, 1984.
[Lev86] H.J. Levesque. Knowledge representation and reasoning. Annual Review of Computer Science, 1:255-287, 1986.
[Lev90] H.J. Levesque. All I know: A study in Autoepistemic Logic. Artificial Intelligence 42,3/4, (1990) pp. 263-309.
[Lew73] D. Lewis. Counterfactuals. Oxford University Press, 1973.
[Lif85] V. Lifschitz. Computing circumscription. In Proceedings of IJCAI-85, pages 121-127, 1985.
[Lif86] V. Lifschitz. Pointwise circumscription: a preliminary report. In Proc. Amer. Assoc. for Art. Intell. National Conf., pages 406-410, Philadelphia, 1986.
[Lif89a] V. Lifschitz. Benchmark problems for formal nonmonotonic reasoning. In Nonmonotonic Reasoning: 2nd Intl. Workshop, pages 202-217, 1989. (Lecture Notes in Artificial Intelli- gence 346).
[Lif89b] V. Lifschitz. Between circumscription and autoepistemic logic. Research Report, Stanford University, Stanford, CA (1989).
[Lif91] V. Lifschitz. Nonmonotonic databases and epistemic queries: Preliminary report. In Pro- ceedings of 12th International Joint Conference on Artificial Intelligence, 381-386, Sydney, Australia, 1991.
[Llo87] J.W. Lloyd. Foundations of Logic Programming, Springer-Verlag, Second Edition, 1987.
[Lob90] J. Lobo. On constructive negation for disjunctive logic programs. In Proc. North American Conference on Logic Programming, 704-718, Austin, Texas, 1990.
[Luk90] W. Lukaszewicz Non-monotonic reasoning Ellis-Horwood, Chichester, West Sussex, Eng- land, 1990.
[MD80] D. McDermott and J. Doyle. Non-monotonic logic I. Artificial Intelligence 25, pages 41-72, 1980.
[MD82] D. McDermott and J. Doyle. Non-monotonic logic II. Journal of the ACM, 29, pages 33-57, 1982.
[MH69] J. McCarthy and P.J. Hayes. Some philosophical problems from the standpoint of artificial intelligence. In B. Meltzer and D. Michie, editors, Machine Intelligence 4, pages 463-502. Edinburgh University Press, 1969.
[MLR91] J. Minker, J.Lobo, and A. Rajasekar. Circumscription and Disjunctive Logic Program- ming. In Artificial Intelligence and Mathematical Theory of Computation, Papers in Honor of John McCarthy, 281-305, Academic Press, 1991.
[MNR90] W. Marek, A. Nerode, and J. Remmel. A theory of non-monotonic rule systems, part i (preliminary version). In Proc. 1990 Intl. Symp. on Logic in Computer Science, IEEE, 1990. Annals of Math. and AI. (to appear).
[MNR92] V. Marek, A. Nerode, and J.B. Remmel. The stable models of a predicate logic program. In Proceedings of the Joint International Conference and Symposium on Logic Programming, pages 446-460, 1992.
[MP85] J. Minker and D. Perlis. Computing protected circumscription. Journal of Logic Program- ming, 2(4):235-249, December 1985.
[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 Proceedings of the Seventh International Symposium on Methodologies for Intelligent Systems, Norway, June 1993.
[MS91] W. Marek and V.S. Subrahmanian. The relationship between stable, supported, default and auto-epistemic semantics for general logic programs. Theoretical Computer Science, v.103(2), 365-386, Sept. 1992.
[MS92] W. Marek and V.S. Subrahmanian. The relationship between stable, supported, default and autoepistemic semantics for general logic programs. Theoretical Computer Science, 103:365-386, 1992.
[MT89] W. Marek and M. Truszczy'nski. Relating autoepistemic and default logic. In Proceed- ings of the First International Conference on Principles of Knowledge Representation and Reasoning (KR-89), pages 276-288, Toronto, Ontario, 1989.
[MT91] V. Marek and M. Truszczynski. Autoepistemic logic. Journal of ACM, 38(3), 588-619, July 1991.
[MT92] V. Marek and M. Truszczynski. More on modal aspects of default logic. Fundamenta Informaticae, 17:99-116, 1992.
[MT93] V. Marek and M. Truszczynski. Nonmonotonic Logic - Context-Dependent Reasonings Springer Verlag, 1993
[MZ82] J. Minker and G. Zanon. An extension to linear resolution with selection function. Infor- mation Processing Letters, 14(3):191-194, June 1982.
[McC58] J. McCarthy. Programs with common sense. Mechanization of Thought Processes, Pro- ceedings of the Symposium of the National Physics Laboratory, vol. 1, 77-84. London. Reprinted in Semantic Information Processing, pages 403-418. The MIT Press, Cam- bridge, MA, 1968, 1958.
[McC77] J. McCarthy. Epistemological problems of artificial intelligence. In Pro. Int. Joint. Conf. on Art. Intell., pages 223-227, Cambridge, MA, 1977.
[McC80] J. McCarthy. Circumscription - a form of non-monotonic reasoning. Artificial Intelligence, 13:27-39, 1980.
[McC91] J. McCarthy. Artificial Intelligence and Mathematical Theory of Computation, Papers in Honor of John McCarthy ed. V. Lifschitz, Academic Press, 1991.
[Min82] J. Minker. On indefinite databases and the closed world assumption. In Proceedings of 6th Conference on Automated Deduction, pages 292-308, New York, 1982.
[Min88] J. Minker. (editor) Foundations of Deductive Databases and Logic Programming. Morgan Kaufmann, 1988 .
[Min88] J. Minker. Perspectives in deductive databases. Journal of Logic Programming, 5:33-60, 1988.
[Mins74] M. Minsky. A framework for representing knowledge. Technical Report 306, MIT Artificial Intelligence Laboratory, 1974. Reprinted without appendix in The Psychology of Computer vision, P. Winston (ed.), 177-211, McGraw-Hill (1975).
[Mins91] M. Minsky. Logical versus analogical or symbolic versus connectionist or neat versus scruffy. AI Magazine, 12(2):34-51, 1991.
[Min91] J. MinkerAn overview of nonmonotonic reasoning and logic programming. University of Maryland Technical Report, UMIACS TR-91-112, CS-TR-2736, 31pp., August 1991.
[Moo85a] R. Moore. Semantical considerations on nonmonotonic logic. Artificial Intelligence, 25(1):75-94, 1985.
[NNS92] A. Nerode, R. Ng, and V.S. Subrahmanian. Computing circumscriptive databases, part i: Theory and algorithms. Information and Computation. to appear.
[NS91] R. Ng and V.S. Subrahmanian. Relating dempster-shafer to stable semantics. In Interna- tional Symposium on Logic Programming, pages 551-566, 1991.
[NS92] R. Ng and V.S. Subrahmanian. Dempster-shafer logic programs and stable semantics. 1992. Submitted.
[Nie92] I.N.F. Niemela. On the decidability and complexity of autoepistemic reasoning. Funda- menta Informaticae, 17:117-155, 1992.
[PAA91] L.M. Pereira, J.N. Aparico, and J.J. Alferes. Counterfactual reasoning based on revising assumptions. In International Symposium on Logic Programming, pages 566-577, 1991.
[PGA] D. Poole, R. Goebel, and R. Aleliunas. Theorist: A logical system for defaults and diag- nosis. In N. Cercone and G. McCalla, editors, The Knowledge Frontier, pages 331-352. Springer, 1987.
[PM86] D. Perlis and J. Minker. Completeness results for circumscription. Artificial Intelligence, 28(1):29-42, 1986.
[PR90] Y. Peng and J. Reggia Abductive inference methods for diagnostic problem solving. Springer-Verlag, 1990.
[PS92] C.H. Papadimitriou and M. Sideri. On finding extensions of default theories. In Interna- tional Conference on Database Theory: Lecture Notes in Computer Science 646, Springer Verlag, pages 276-281, 1992.
[Pea88] J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, Los Altos, California, 1988.
[Per86] D. Perlis. On the consistency of commonsense reasoning. Computational Intelligence, 2:180-190, 1986.
[Per87] D. Perlis. Circumscribing with sets. Artificial Intelligence, 31:201-211, 1987.
[Per88] D. Perlis. Autocircumscription. Artificial Intelligence, 36(2):223-236, 1988.
[Phi91] G. Phipps. Glue Manual, Version 1.0. Technical Report, Dept. of Computer Science, Stanford University, Feb. 1991.
[Prz88] T.C. Przymusinski. On the declarative semantics of deductive databases and logic pro- gramming. In J. Minker, editor, Foundations of Deductive Databases and Logic Program- ming, pages 193-216. Morgan Kaufmann Pub., 1988.
[Prz89] T. C. Przymusinski. An algorithm to compute circumscription. Artificial Intelligence, 38:49-73, 1989.
[Prz89a] T. C. Przymusinski. The well-founded semantics coincides with the three-valued stable semantics. Fundamenta Informaticae, 1989.
[Prz90] T. Przymusinski. Stationary semantics for disjunctive logic programs and deductive databases. In S. Debray and M. Hermenegildo, editors, Proc. of the North American Conference on Logic Programming, 40-59, Austin, Texas, Oct. 1990.
[Prz91a] T. C. Przymusinski Autoepistemic logic of closed beliefs and logic programming. In: Pro- ceedings of the First International Workshop on Logic Programming and nonmonotonic Reasoning. A. Nerode, W. Marek, and V.S. Subrahmanian, editors. MIT Press, 1991 3-20.
[Prz91b] T. Przymusinski. Stable semantics for disjunctive programs. New Generation Computing, 9:401-42, 1991.
[RC81] R. Reiter and G. Criscuolo. On interacting defaults. In Proceedings of IJCAI-81, pages 270-276, 1981.
[RD87] R. Reiter and J. de Kleer. Formal foundations for assumption-based truth maintenance systems: preliminary report. In Proceedings of AAAI 87, 183-188, Seattle, Washington, July, 1987.
[RLM89] A. Rajasekar, J. Lobo, and J. Minker. Weak generalized closed world assumption. Journal of Automated Reasoning, 5:293-307, 1989.
[RSS92] R. Ramakrishnan, D. Srivastava and S. Sudarshan CORAL_Control, Relations and Logic Proceedings of the 18th International Conference on Very Large Databases, L.-Y. Yuan, editor, 238-250, Vancouver, Canada, 1992.
[RT88] K.A. Ross and R.W. Topor. Inferring negative information from disjunctive databases. Journal of Automated Reasoning, 4(2):397-424, December 1988.
[Rap71] B. Raphael. The frame problem in problem solving systems. In N. Findler and B. Meltzer, editors, Artificial Intelligence and Heuristic Programming, pages 159-169, New York, 1971. American Elsevier.
[Rei78a] R. Reiter. On Closed World Data Bases. In Logic and Data Bases, eds. H. Gallaire and J. Minker, 55-76, Plenum, New York, 1978.
[Rei78b] R. Reiter. On reasoning by default. In Proceedings of TINLAP-2, Theoretical Issues in Nat- ural Language Processing-2, pages 210-218, University of Illinois at Urbana-Champaign, 1978.
[Rei80a] R. Reiter. A logic for default reasoning. Artificial Intelligence, 13(1 and 2):81-132, April 1980.
[Rei82] R. Reiter. Circumscription implies predicate completion (sometimes). Proc. Amer. Assoc. for Art. Intell. National Conference, pages 418-420, 1982.
[Rei87] R. Reiter. Nonmonotonic reasoning. Annual Review of Computer Science, 2:147-186, 1987.
[Rei90] R. Reiter. On asking what a database knows. In J. Lloyd, editor, Computational Logic: Symposium Proceedings. Springer-Verlag, 1990.
[Rob65] J.A. Robinson. A machine-oriented logic based on the resolution principle. Journal of the ACM, 12(1), 23-41, Jan. 1965.
[Ros89] K. Ross. Well-founded semantics for disjunctive logic programs. In Proc. of the first International Conference on Deductive and Object Oriented Databases, 352-369, Kyoto, Japan, Dec. 4-6,1989.
[SI92] K. Satoh and N. Iwayama. A query evaluation method for abductive logic programming. In Proceedings of the Joint International Conference and Symposium on Logic Programming, pages 671-685, 1992.
[SK91] B. Selman and H. Kautz. Knowledge compilation using Horn approximations. In Proceed- ings of AAAI-91, 904-909, AT&T Bell Laboratories, Murray Hill, NJ 07974, 1991.
[SL88] V . S . Subrahmanian and J. Lu. Protected completions of first order general logic pro- grams. Journal of Automated Reasoning, 6(2), 147-172, June 1990.
[SL89] B. Selman and H.J. Levesque. The tractability of path-based inheritance. In Proceedings IJCAI-89, pages 1140-1145, Detroit, MI, 1989.
[SL90] B. Selman and H.J. Levesque. Abductive and default reasoning: A computational core. In Proc. of the Eighth National Conference on Artificial Intelligence, 343-348, 1990.
[SNV92] V.S. Subrahmanian, D. Nau, and C. Vago. Wfs + branch and bound = stable models. Technical report, Dept. of Computer Science, University of Maryland at College Park, 1992.
[San85] E. Sandewall. An approach to the frame problem and its implementation. In Machine Intelligence 7, pages 195-204. Edinburgh University Press, 1985.
[Sch87] J.S. Schlipf. Decidability and definability with circumscription. Intl. Annals of Pure and Applied Logic, 35(2):173-191, 1987.
[Sch88] J.S. Schlipf. When is closed world reasoning tractable? In Proc. of the 3rd International Symposium on Methodologies for Intelligent Systems(ISMIS-88), 485-494, 1988.
[Sch90] J.S. Schlipf. The expressive powers of the logic programming semantics. In Proc. of the Ninth Conference on Principles of Database Systems (PODS-90), 196-204, 1990.
[Sel90] B. Selman. Tractable Defeasible Reasoning. PhD thesis, Computer Science Department, University of Toronto, 1990.
[She88] J.C. Shepherdson. Negation in logic programming. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 19-88. Morgan Kaufman Pub., 1988.
[Shv90] G. Shvarts Autoepistemic modal logics Proceedings TARK-1990, Ed. R. Parikh, pp. 97-109, Morgan Kaufmann, publishers, 1990
[Smy78] M. Smyth Power domains. Journal of Computer and System Sciences, 16(1), pp. 23-36, 1978.
[Sta68] R. Stalnaker. A theory of conditionals. Studies in Logical Theory, American Philosophical Quarterly Monograph Series, No. 2, 1968.
[TG91] S. Tsur and N. Garrison. LDL User's Guide, Edition 1 MCC Technical Report Number: STP-LD-295-91, Aug. 91.
[TS86] H. Tamaki and T. Sato OLD resolution with tabulation. In: Proceedings of the Third International Conference on Logic Programming, 84-98, 1986.
[Tou84] D.S. Touretzky. The Mathematics of Inheritance Systems. Morgan Kaufmann, Los Altos, CA. 1986.
[Tru91] M. Truszczy'nski. Embedding default logic into modal non-monotonic logics. In A. Nerode, W. Marek, and V.S. Subrahmanian, editors, Logic Programming and Non-monotonic Rea- soning: Proceedings of the First International Workshop, pages 151-165. MIT Press, 1991.
[VG88] A. Van Gelder. Negation as failure using tight derivations for general logic programs. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 149-176. Morgan Kaufmann, 1988.
[VG89] A. Van Gelder The alternating fixpoint of logic programs with negation. Proceedings of the Eighth ACM Symposium on Principles of Database Systems, 1-10, 1989.
[VRKSS90] J. Vaghani, K. Ramamohananrao, D. Kemp, Z. Somogyi, and P. Stuckey. Design overview of the Aditi deductive database system. Tech. Report, Dept. of Computer Science, Univ. of Melbourne, July 1990.
[VRS88] A. Van Gelder, K. Ross, and J.S. Schlipf. Unfounded sets and well-founded semantics for general logic programs. In Proc. 7th Symposium on Principles of Database Systems, pages 221-230, 1988.
[Wey80] R.W. Weyrauch. Prologomena to a theory of mechanized formal reasoning. Artificial Intelligence, 13(1 and 2):133-170, April 1980.
[Win80] T. Winograd. Extended inference modes in reasoning by computer systems. Artificial Intelligence, 13(1 and 2):5-26, April 1980.