%0 Journal Article
%T THE ALGORITHM AND COMPLEXITY OF PROPOSITIONAL KNOWLEDGE BASE REVISION<br>命题知识库更新的算法及其复杂性
%A Tao Xuehong
%A Sun Wei
%A Ma Shaohan
%A <br>陶雪红
%A 孙伟
%A 马绍汉
%J 软件学报
%D 1996
%I 
%X This paper gives an outline of knowledge base revision and some recently presented complexity results about propositional knowledge base revision. Different methods for revising propositional knowledge base have been proposed recently by several researchers, some are formula--based methods and the others are model-based methods, but all methods are intractable in the general case. This paper discusses a formula-based method-Ginsberg's method, and presents a polynomial algorithm when the number of formulas is far less than the number of variables.
%K Artificial intelligence
%K knowledge base revision
%K algorithmic complexity
%K SAT problem
%K propositional logic<br>人工智能
%K 知识库更新
%K 算法复杂性
%K 可满足性问题
%K 命题逻辑
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=EE19857B877AAC899D2BCFCE36396648&yid=8A15F8B0AA0E5323&vid=DF92D298D3FF1E6E&iid=94C357A881DFC066&sid=B1E36BF7B9783A85&eid=407C905D8F0449C4&journal_id=1000-9825&journal_name=软件学报&referenced_num=2&reference_num=7