Journal of the ACM Bibliography

Georg Gottlob. Translating default logic into standard autoepistemic logic. Journal of the ACM, 42(4):711-740, July 1995. [BibTeX entry]

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\'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

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database