| 摘要: |
| 本文介绍了知识库更新的基本概念及命题知识库更新的复杂性研究现状．近年来，学者们提出了许多方法进行命题知识库的更新，一类是基于公式的方法；一类是基于模型的方法，但所有这些方法在通常情况下都是难解的．本文讨论基于公式的Ｇｉｎｓｂｅｒｇ更新方法，并给出在公式个数远小于变元个数情况下的一个多项式时间算法． |
| 关键词: 人工智能 知识库更新 算法复杂性 可满足性问题 命题逻辑 |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到国家自然科学基金资助. |
|
| THE ALGORITHM AND COMPLEXITY OF PROPOSITIONAL KNOWLEDGE BASE REVISION |
|
Tao Xuehong,Sun Wei,Ma Shaohan
|
| Abstract: |
| 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. |
| Key words: Artificial intelligence knowledge base revision algorithmic complexity SAT problem propositional logic. |
