AbstractSince Konolige's translation of default logic into strongly grounded autoepistemic logic (Artificial Intelligence 35:343-382 (1988)) several other variants of Moore's original autoepistemic logic that embody default logic have been studied. All these logics differ significantly from Moore's autoepistemic logic (standard AEL) in that expansions are subject to additional groundedness-conditions. Hence, the question naturally arises whether default logic can be translated into standard AEL at all. We show that a modular translation is not possible. However, we are able to construct a faithful polynomial-time translation from default logic into standard AEL which is nonmodular. Our translation exploits the self-referentiality of AEL. It uses as important intermediate step an embedding of Marek's and Truszczy\'nski's nonmonotonic logic N into standard AEL. It follows from our results that the expressive power of standard AEL is strictly greater than that of default logic. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic -- Computational Logic; I.2.0 [Artificial Intelligence] -- philosophical foundation; I.2.3 [Artificial Intelligence]: Deduction and Theorem Proving -- Nonmonotonic reasoning and belief revision; I.2.4 [Artificial Intelligence]: Knowledge Representation Formalisms and Methods -- representation languages
General Terms: Theory
Additional Key Words and Phrases: Autoepistemic logic, default logic, nonmonotonic modal logic, reasoning, translation
Selected papers that cite this one
- Francesco M. Donini, Daniele Nardi, and Riccardo Rosati. Ground nonmonotonic modal logics. Journal of Logic and Computation, 7(4):523-548, August 1997.
- Francesco M. Donini, Daniele Nardi, and Riccardo Rosati. Ground nonmonotonic modal logics. Journal of Logic and Computation, 7(4):523-548, August 1997.
- Joseph Y. Halpern. A theory of knowledge and ignorance for many agents. Journal of Logic and Computation, 7(1):79-108, February 1997.
Selected references
- Marco Cadoli and Marco Schaerf. A survey of complexity results for nonmonotonic logics. Journal of Logic Programming, 17(2/3-4):127-160, November 1993.
- Wiktor Marek and Miroslaw Truszczynski. Autoepistemic logic. Journal of the ACM, 38(3):588-619, July 1991.
- Drew McDermott. Nonmonotonic logic II: Nonmonotonic modal theories. Journal of the ACM, 29(1):33-57, January 1982.