Grigoris Antoniou
Abstract
Default logic is one of the most prominent approaches to nonmonotonic reasoning, and allows one to make plausible conjectures when faced with incomplete information about the problem at hand. Default rules prevail in many application domains such as medical and legal reasoning.
Several variants have been developed over the past year, either to overcome some perceived deficiencies of the original presentation, or to realize somewhat different intuitions. This paper provides a tutorial-style introduction to some important approaches of Default Logic. The presentation is based on operational models for these approaches, thus making them easily accessible to a broader audience, and more easily usable in practical applications.
- ANTONIOU, G., O'NEILL, T., AND THURBON, J. 1996. Studying properties of classes of default logics: Preliminary report. In Proceedings of the Fourth Pacific Rim International Conference on Artificial Intelligence, Springer-Verlag, New York, 558-569. Google Scholar
Digital Library
- ANTONIOU, G. AND SPERSCHNEIDER, V. 1994. Operational concepts of nonmonotonic logics. Part 1: Default logic. Artif. Intell. Rev. 8, 3-16.Google ScholarCross Ref
- BAADER, F. AND HOLLUNDER, B. 1993. How to prefer more specific defaults in terminological logics. In Proceedings of the 13th International Joint Conference on Artificial Intelligence, MIT Press, Cambridge, MA.Google Scholar
- BESNARD, P. 1989. An Introduction to Default Logic. Springer-Verlag, Vienna, Austria. Google ScholarDigital Library
- BESNARD, P. AND SCHAUB, T. 1994. possible worlds semantics for default logics. Fundam. Inf. 21, 39-66.Google ScholarDigital Library
- BONDARENKO, A., DUNG, P. M., KOWALSKI, R. A., AND TONI, F. 1997. An abstract, argumentation-theoretic approach to default reasoning. Artif. Intell. 93, 1-2, 63-101. Google ScholarDigital Library
- BREWKA, G. 1991. Cumulative default logic: in defense of nonmonotonic inference rules. Artif. Intell. 50, 2 (July 1991), 183-205. Google ScholarDigital Library
- BREWKA, G. 1994. Reasoning about priorities in default logic. In Proceedings of the 12th National Conference on Artificial Intelligence (vol. 2) (AAAI'94, Seattle, WA, July 31-Aug. 4), B. Hayes-Roth and R. E. Korf, Eds. Amer. Assn. for Artificial Intelligence, Menlo Park, CA, 940-945. Google ScholarDigital Library
- CADOLI, M., DONINI, F. M., AND SCHAERF, M. 1994. Is intractability of non-monotonic reasoning a real drawback?. In Proceedings of the 12th National Conference on Artificial Intelligence (vol. 2) (AAAI'94, Seattle, WA, July 31-Aug. 4), B. Hayes-Roth and R. E. Korf, Eds. Amer. Assn. for Artificial Intelligence, Menlo Park, CA, 946-951. Google ScholarDigital Library
- CHOLEWINSKI, P. 1994. Stratified default logic. In Proceedings of the Conference on Computer Science Logic, Springer-Verlag, New York, 456-470. Google ScholarDigital Library
- CHOLEWINSKI, P., MAREK, W., MIKITIUK, A., AND TRUSZCZYNSKI, M. 1995. Experimenting with default logic. In Proceedings of the International Conference on Logic Programming, MIT Press, Cambridge, MA.Google Scholar
- COURTNEY, A., ANTONIOU, G., AND FOO, N. 1996. Exten: A system for computing default logic extensions. In Proceedings of the Fourth Pacific Rim International Conference on Artificial Intelligence, Springer-Verlag, New York, 471-482. Google ScholarDigital Library
- DELGRANDE, J. P., SCHAUB, T., AND JACKSON, W. K. 1994. Alternative approaches to default logic. Artif. Intell. 70, 1-2 (Oct. 1994), 167-237. Google ScholarDigital Library
- ENGELFRIET, J. AND TREUR, J. 1996. Semantics for default logic based on specific branching time models. In Proceedings of the 12th European Conference on Artificial Intelligence, John Wiley and Sons, Inc., New York, NY, 60-64.Google Scholar
- ETHERINGTON, D W 1987. Formalizing nonmonotonic reasoning systems. Artif. Intell. 31, 1 (Jan. 1987), 41-85. Google ScholarDigital Library
- ETHERINGTON, D. 1987. Reasoning with Incomplete Information. Pitman Publishing, London, UK. Google ScholarDigital Library
- ETHERINGTON, D. AND REITER, R. 1983. On inheritance hierarchies with exceptions. In Proceedings of the National Conference on Artificial Intelligence, AAAI Press, Menlo Park, CA, 104-108.Google Scholar
- GELFOND, M., LIFSCHITZ, V., PRZYMUSINSKA, g., AND TRUSZCZYNSKI, M. 1991. Disjunctive defaults. In Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning, Morgan Kaufmann, San Mateo, CA, 230-237.Google Scholar
- GOTTLOB, G. 1992. Complexity results for nonmonotonic logics. J. Logic Comput. 2, 397-425.Google ScholarCross Ref
- KAUTZ, H. A. AND SELMAN, B. 1989. Hard problems for simple default logics. In Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, R. J. Brachman, H. J. Levesque, and R. Reiter, Eds. Morgan Kaufmann Publishers Inc., San Francisco, CA, 189-197. Google ScholarDigital Library
- LINKE, T AND SCHAUB, T. 1995. Lemma handling in default logic theorem proving. In Proceedings of the Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, Springer-Verlag, New York, 285-292. Google ScholarDigital Library
- LUKASZEWICZ, W. 1988. Considerations on default logic. Comput. Intell. 4, 1, 1-16.Google ScholarCross Ref
- LUKASZEWICZ, W. 1990. Non-Monotonic Reasoning: Formalization of Commonsense Reasoning. Ellis Horwood, Upper Saddle River, NJ.Google Scholar
- MAKINSON, D. 1994. General patterns in nonmonotonic reasoning. In Handbook of Logic in Artificial Intelligence and Logic Programming: Nonmonotonic Reasoning and Uncertain Reasoning (vol. 3), D. M. Gabbay, C. J. Hogger, and J. A. Robinson, Eds. Oxford University Press, Inc., New York, NY, 35-110. Google ScholarDigital Library
- MAREK, V. AND TRUSZCZYNSKI, M. 1993. Nonmonotonic Reasoning. Springer-Verlag, New York, NY.Google Scholar
- MCCARTHY, J. 1980. Circumscription: A form of non-monotonic reasoning. Artif. Intell. 13, 27-39.Google ScholarDigital Library
- MIKITIUK, A. AND TRUSZCZYNSKI, M. 1995. Constrained and rational default logics. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, San Mateo, CA, 1509-1515. Google ScholarDigital Library
- MOORE, R. C. 1985. Semantical considerations on nonmonotonic logic. Artif. Intell. 25, 1 (Jan. 1985), 75-94. Google ScholarDigital Library
- NIEMELA, I. 1995. Towards efficient default reasoning. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, San Mateo, CA, 312-318. Google ScholarDigital Library
- PEARL, g. 1990. System z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning. In Proceedings of the Third International Conference on Theoretical Aspects of Reasoning about Knowledge, Springer-Verlag, New York, NY. Google ScholarDigital Library
- POOLE, D. 1994. Default logic. In Handbook of Logic in Artificial Intelligence and Logic Programming: Nonmonotonic Reasoning and Uncertain Reasoning (vol. 3), D. M. Gabbay, C. J. Hogger, and J. A. Robinson, Eds. Oxford University Press, Inc., New York, NY, 189-215. Google ScholarDigital Library
- REITER, R. 1978. On closed world databases. In Logic and Data Bases, H. Gallaire and J. Minker, Eds. Plenum Press, New York, NY, 55-76.Google Scholar
- REITER, R. 1980. A logic for default reasoning. Artif. Intell. 13, 81-132.Google ScholarDigital Library
- RISCH, V. AND SCHWIND, C. 1994. Tableau-based characterization and theorem proving for default logic. J. Autom. Reasoning 13, 223-242.Google ScholarCross Ref
- SCHAUB, T. 1992. On constrained default theories. In Proceedings of the l Oth European Conference on Artificial Intelligence (ECAI '92, Vienna, Austria, Aug. 3-7), B. Neumann, Ed. John Wiley and Sons, Inc., New York, NY, 304-308. Google ScholarDigital Library
- SCHAUB, T. 1995. A new methodology for queryanswering in default logics via structure-oriented theorem proving. J. Autom. Reasoning 15, 1, 95-165.Google ScholarCross Ref
- TENG, C. 1996. Possible world partition sequences: A unifying framework for uncertain reasoning. In Proceedings of 12th Conference on Uncertainty in Artificial Intelligence, 517-524. Google ScholarDigital Library
- TOURETZKY, D., HORTY, J., AND THOMASON, R. 1987. A clash of intuitions: The current state of nonmonotonic multiple inheritance systems. In Proceedings of the l Oth International Joint Conference on Artificial Intelligence, MIT Press, Cambridge, MA, 476-482.Google Scholar
Index Terms
- A tutorial on default logics
Recommendations
Expressing Default Logic Variants in Default Logic
Reiter's default logic is one of the best known and most studied of the approaches to nonmonotonic reasoning. Several variants of default logic have subsequently been proposed to give systems with properties differing from the original. In this paper, ...
An Interpretation of Default Logic in Minimal Temporal Epistemic Logic
When reasoning about complex domains, where information available is usually only partial, nonmonotonic reasoning can be an important tool. One of the formalisms introduced in this area is Reiter‘s Default Logic (1980). A characteristic of this formalism is ...
Reviews
Doris C. Appleby
Antoniou continues the generally excellent series of surveys published by the ACM for over 30 years. Each is intended for upper-level undergraduates or beginning graduate students, and describes a particular area of computer science. This tutorial focuses on the basic concepts of default reasoning, which is the logic that applies to a system that has only incomplete information at hand, and where plausible conjectures called defaults are added to the premises being assumed. If new information later becomes available, the default and any conclusions depending on its use may be retracted. Such a system is nonmonotonic. That is, if a statement s follows from a set of premises M , and M?M ? , then s does not necessarily follow from M ? . Only a general familiarity with the predicate calculus is assumed. The <__?__Pub Caret>monograph is based on work beginning with that of <__?__Pub Fmt nolinebreak>Reiter<__?__Pub Fmt /nolinebreak> (1980), continuing through Lukaszewicz (1988–90), and ending with the Rational Default Logic of Mikitiuk and <__?__Pub Fmt nolinebreak>Trusczynski <__?__Pub Fmt /nolinebreak>(1995). A 1996 paper of Engelfriet and Treur on the semantics of default logics is included in the excellent reference list, but statement meanings are not discussed in this tutorial. A simple example neatly explains the difference between a default logic and classical logic (p.<__?__Pub Fmt interword-space>339). Default logic uses football: ¬ snow takesPlace , whereas classical has football ? ¬ snow ? takesPlace . In the first rule, ¬ snow is used as a default, whereas in the second, it is a fact. Classical reasoning would prohibit any football games from being scheduled unless it were “proven” that there would be no snow, while using a default allows games to be listed assuming that there will be no snow. Although this example was well chosen, others are old chestnuts, such as the bird tweety series. I was disappointed by the lack of motivation for using default logics in real-world situations, such as databases, law, and medicine, as the author claims. The tweety example is not sufficient. The author states that the purpose of this tutorial is to contribute to “the understanding of the basic concepts” (p.<__?__Pub Fmt interword-space>358), and he refers readers to specific references discussing implementations. He notes that default reasoning has proven difficult for students at the University of Toronto to understand. I believe that the inclusion of better examples would have helped.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments