Fixed—Parameter Tractability of Disjunction—Free Default Reasoning  

作　　者：赵希顺 丁德成 

机构地区：[1]InstituteofLogicandCognition,ZhongshanUniversity,Guangzhou510275,P.R.China [2]DepartmentofMathematics,NanjingUniversity,Nanjing210093,P.R,China

出　　处：《Journal of Computer Science & Technology》2003年第1期118-124,共7页计算机科学技术学报（英文版）

基　　金：the MOE project "Computational Complexity of Intelligent Reasoning"，国家自然科学基金

摘　　要：In this paper, the parameter which is the source of the complexity of disjunctionfree default reasoning is determined. It is shown that when the value of this parameter is fixed, the disjunction-free default reasoning can be solved in time bounded by a polynomial whose degree does not depend on the parameter. Consequently, disjunction-free default reasoning is fixed parameter tractable.

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]