Journal of the Association for Computing Machinery, Vol. 42, No. 4, July 1995, pp. 711–740.

Translating Default Logic into Standard Autoepistemic Logic

GEORG GOTTLOB

Abstract. Since 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ński’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.

Categories and Subject Descriptors. F.4.1 [Computational Logic]; I.2.0 [philosophical foundation]; I.2.3 [Nonmonotonic reasoning and belief revision]; I.2.4 [representation languages]

General Terms. Theory

Additional Key words and Phrases. Autoepistemic logic, default logic, nonmonotonic modal logic, reasoning, translation

Copyright 1995 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.