Default Logic - Translations

Translations

Default theories can be translated into theories in other logics and vice versa. The following conditions on translations have been considered:

Consequence-Preserving

the original and the translated theories have the same (propositional) consequences;

Faithful

this condition only makes sense when translating between two variants of default logic or between default logic and a logic in which a concept similar to extension exists, e.g., models in modal logic; a translation is faithful if there exists a mapping (typically, a bijection) between the extensions (or models) of the original and translated theories;

Modular

a translation from default logic to another logic is modular if the defaults and the background theory can be translated separately; moreover, the addition of formulae to the background theory only leads to adding the new formulae to the result of the translation;

Same-Alphabet

the original and translated theories are built on the same alphabet;

Polynomial

the running time of the translation or the size of the generated theory are required to be polynomial in the size of the original theory.

Translations are typically required to be faithful or at least consequence-preserving, while the conditions of modularity and same alphabet are sometimes ignored.

The translatability between propositional default logic and the following logics have been studied:

• classical propositional logic;
• autoepistemic logic;
• propositional default logic restricted to seminormal theories;
• alternative semantics of default logic;
• circumscription.

Translations exist or not depending on which conditions are imposed. Translations from propositional default logic to classical propositional logic cannot always generate a polynomially sized propositional theory, unless the polynomial hierarchy collapses. Translations to autoepistemic logic exists or not depending on whether modularity or the use of the same alphabet is required.