Affiliations: Department of Computer Science, University of Kentucky, Lexington, KY 40506-0027, E-mails: marek@ms.uky.edu, mirek@ms.uky.edu
Note: [1] Parts of this paper appeared earlier in the extended abstract Relating Autoepistemic and Default Logics, published in the Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, KR89, Morgan-Kaufmann, 1989.
Note: [*] This work was partially supported by National Science Foundation under grant IRI-9012902, National Science Foundation and the Commonwealth of Kentucky EPSCoR program under grant RII8610671.
Abstract: Investigations of default logic have been so far mostly concerned with the notion of an extension of a default theory. It turns out, however, that default logic is much richer. Namely, there are other natural classes of objects that might be associated with default reasoning. We study two such classes of objects with emphasis on their relations with modal nonmonotonic formalisms. First, we introduce the concept of a weak extension and study its properties. It has long been suspected that there are close connections between default and autoepistemic logics. The notion of weak extension allows us to precisely describe the relationship between these two formalisms. In particular, we show that default logic with weak extensions is essentially equivalent to autoepistemic logic, that is, nonmonotonic logic KD45. In the paper we also study the notion of a set of formulas closed under a default theory. These objects are shown to correspond to stable theories and to modal logic S5. In particular, we show that skeptical reasoning with sets closed under default theories is closely related with provability in S5. As an application of our results we determine the complexity of reasoning with weak extensions and sets closed under default theories.
