TRANSLATING DEFAULT LOGIC INTO STANDARD AUTOEPISTEMIC LOGIC

Since Konolige's translation of default logic into strongly grounded a utoepistemic logic (Artif. Int. 35, 1988, pp. 343-382), several other variants of Moore's original autoepistemic logic that embody default l ogic have been studied. All these logics differ significantly from Moo re'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 al l. 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 exploit s the self-referentiality of AEL. It uses as an important intermediate step an embedding of Marek's and Truszczynski's nonmonotonic logic N into standard AEL. It follows from our results that the expressive pow er of standard AEL is strictly greater than that of default logic.