On the expressive power of semi‐normal defaults in some semantic variants of default logic

Issue title: Artificial Intelligence Advances in China

Article type: Research Article

Authors: Mingyi, Zhang | Ying, Zhang

Affiliations: Guizhou Academy of Sciences, Guiyang, 550001, P. R. China E‐mail: zhangmy@mail.guz.cei.gov.cn

Abstract: Normality, semi‐normality and prerequisite‐freedom are examples of syntactic restrictions proposed for defaults. The expressive powers of Reiter's default logic under the corresponding syntactic restrictions have been analyzed by Janhunen. It is quite natural that to ask if such restrictions affect the expressive power of variants of default logic. In this paper we analyze the expressive powers of semi‐normal (SN) variants of Lukaszewicz's default logic (LDL). Among another variants of default logic are cumulative default logic (CDL) by Brewka as well as commitment to assumptions default logic and quasi‐default logic (CADL and QDL) by Giordano and Martelli. The expressive powers of these three variants under the corresponding syntactic restrictions are also investigated. The framework is based on the notion of Janhunen's polynomial, faithful and modular (PFM) translation function that maps systematically theories of one nonmonotonic logic to theories of other such that the semantics of theories is preserved. The criteria for evaluating expressive powers of nonmonotonic logics are existence/nonexistence of PFM translations between such nonmonotonic logics. According to the measure provided by PFM translation we point out that semi‐normality, in general (allowing defaults possessing no consistency conditions) may decrease expressive power of defaults in LDL and prove that semi‐normality does not affect expressiveness of defaults in LDL* (where defaults have at least one consistency condition). For assertion default theories, expressive power may decrease in certain DL variants if syntactic resections (such as semi‐normality) are introduced. The reason why such anomalies arise is that consistency conditions of applied defaults are recorded in the support of extensions. To deal with this problem we introduce a weaker notion of PFM translation function, called quasi‐PFM translation function (QPFM). According to the measure provided by QPFM translations we analyze expressive powers of semi‐normal defaults in CDL, CADL and QDL and establish that, in CDL and QDL, semi‐normality does not affect expressiveness of defaults yet. For CADL, unfortunately, semi‐normal defaults are less expressive than general defaults even if we adopt a weaker notion of faithfulness than one by Janhunen. Noticing that arbitrary consistency conditions (including empty consistency condition) are allowed for LDL, CADL and QDL, we also consider the possibility of reducing multiple consistency conditions to a single consistency condition.

Journal: AI Communications, vol. 16, no. 1, pp. 51-67, 2003