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

摘要

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.