Evaluating the effect of semi-normality on the expressiveness of defaults

T Janhunen - Artificial Intelligence, 2003 - Elsevier
Artificial Intelligence, 2003Elsevier
Normal default logic (NDL) and semi-normal default logic (SNDL) are syntactically restricted
variants of Reiter's default logic (DL). Although semi-normal defaults have only a slightly
more general form than normal defaults, SNDL does not share the nice properties of NDL
(eg, semi-monotonicity). In this note, we address the effect of semi-normality on the
expressive power of defaults, using a classification method based on polynomial, faithful,
and modular (PFM) translation functions. The resulting classification indicates that SNDL …
Normal default logic (NDL) and semi-normal default logic (SNDL) are syntactically restricted variants of Reiter's default logic (DL). Although semi-normal defaults have only a slightly more general form than normal defaults, SNDL does not share the nice properties of NDL (e.g., semi-monotonicity). In this note, we address the effect of semi-normality on the expressive power of defaults, using a classification method based on polynomial, faithful, and modular (PFM) translation functions. The resulting classification indicates that SNDL and DL are of equal expressive power, which strictly exceeds that of NDL. This strengthens an earlier result achieved by Marek and Truszczyński, who establish the equivalence of weak semi-normal defaults with general defaults. Furthermore, it is established that prerequisite-free fragments of DL and SNDL (PDL and PSNDL) are of equal expressive power. Consequently, PSNDL is less expressive than DL and SNDL, incomparable with NDL, and more expressive than preferential entailment (a generalized form of circumscription). The latter result is in sharp contrast with Imielinski's result, which states that prerequisite-free and semi-normal default theories can be modularly translated into preferential entailment.
Elsevier