缺省逻辑的累积性变种的扩张特征  

ON NEW CUMULATIVE VARIANTS OF DEFAULT LOGIC: CHARACTERIZATION AND ALGORITHMS OF EXTENSIONS

作　　者：张明义[1] 张颖[2] 

机构地区：[1]贵州大学计算机科学系,贵阳550025 [2]贵州科学院,贵阳550001

出　　处：《计算机学报》1998年第2期119-126,共8页Chinese Journal of Computers

基　　金：国家863高技术基金;贵州省自然科学基金

摘　　要：Giordano和Martelli提出了Reiter的缺省逻辑（DL）的两个新变种：CADL（CommitmenttoASSumptionsDefaultLongic）与QDI（Quasi-DefaultLogic），它们都具有累积性，但不再具半单调性，QDL甚至不再承诺预设（Committoassumptions）．本文基于我们已经导出的CDL（Cummula－tiveDefaultLogic）与DL扩张的特征，通过建立CADL扩张与CDL扩张之间以及QDL扩张与DL扩张间的关系，获得了CADL与QDL扩张的新特征．并据此得到相应的主要推理任务的算法及复杂性．Recently, Giordano and Martelli have proposed two new variants ofRelier's default logic (DL): commitment to assumptions default logic (CADL) andquasi-default logic (QDL). The first variant is cumulative and commits toassumptions, like Brewka's cumulative default logic (CDL), but is not semimonotonic.The other one is also cumulative, but does not commit to assumptions, and hence isvery closed to Relier's DL. Unfortunately, Giordano and Martelli have only givenquasi-inductive characterizations of extensions for the two variants. Clearly, it isnot straightforward to derive characterizations, by which algorithms for computingextensions and solving reasoning tasks in CADL and QDL can be gotten easily.This paper establishes a relation between CADL and CDL extensions by applyingthe notion of joint compatibility of a default set. Based on the relation, a newcharacterization is gotten immediately and algorithms for reasoning tasks in CADL arepresented with a sightly difference that the credulous reasoning in CADL is harderthan one in CDL since the membership problem of △= (D,W) is no longer reducedinto one of △R= (DCA[R], WCA[R]). A relation between sets of generatingdefaults for DL extension and ones for QDL extensions is also established. Farther, afinite characterization of QDL extensions is derived by introducing the notion ofQcompatibility, and algorithms and complexity for main reasoning tasks in QDL arealso gotten.

关 键 词：缺省逻辑 累积性 相容性 算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]