Fast Algorithms for Revision of Some Special
Propositional Knowledge Bases
LUAN ShangMin(栾尚敏);DAI GuoZhong(戴国忠)
【期刊名称】《计算机科学技术学报（英文版）》 【年(卷),期】2003(018)003
【摘要】In this paper, the computational complexity of propositional clause set counter-factuals is discussed. It is shown that the computational complexity of propositional clause setcounterfactuals is at the second level of the polynomial hierarchy, and that the computationalcomplexity
of
propositional
Horn
clause
set
counterfactuals is at the first level of the polynomialhierarchy. Furthermore, some polynomial algorithms are presented for some special propositionalclause set, such as the unique satisfiable clause set and the clause set of which only one subset isminimally inconsistent with the input clause whose inconsistency check can be solved in polynomialtime.
【总页数】5页(388-392) 【
关
键
词
】
propositional
base
revision;computational
complexity;polynomial algorithm
【作者】LUAN ShangMin(栾尚敏);DAI GuoZhong(戴国忠)
【作者单位】Institute of Software, The Chinese Academy of Sciences, Beijing 100080, P.R. China;Institute of Software, The Chinese Academy of
Fast Algorithms for Revision of Some Special Propositional Knowledge Bases
