Fixed-parameter tractability of disjunction-free default 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 time bounded by a polynomial whose degree does not depend on the parameter.Consequently,disjunction-free default reasoning is fixed parameter tractable.     

缺省理论中一种获取优先序的方法

引进了一种在缺省理论中提取优先序的方法.与已有方法相比,此方法不仅具有合理性且具有低难度.进而定义了缺省逻辑的优先稳定语义.这种方法在不增加复杂性的情况下,增强了谨慎稳定缺省推理的能力.     

FC-normal and extended stratified logic program

This paper investigates the consistency property of FC-normal logic program and presents an equivalent deciding condition whether a logic program P is an FC-normal program. The deciding condition describes the characterizations of FC-normal program. By the Petri-net presentation of a logic program, the characterizations of stratification of FC-normal program are investigated. The stratification of FC-normal program motivates us to introduce a new kind of stratification, extended stratification, over logic program. It is shown that an extended (locally) stratified logic program is an FC-normal program. Thus, an extended (locally) stratified logic program has at least one stable model. Finally, we have presented algorithms about computation of consistency property and a few equivalent deciding methods of the finite FC-normal program.