| 命题知识库更新的算法及其复杂性 |
| |
| 引用本文： | 陶雪红,孙伟,马绍汉.命题知识库更新的算法及其复杂性[J].软件学报,1996,7(5):300-305. |
| |
| 作者姓名： | 陶雪红 孙伟 马绍汉 |
| |
| 作者单位： | 山东大学计算机系,济南,250100;山东大学计算机系,济南,250100;山东大学计算机系,济南,250100 |
| |
| 基金项目： | 本文研究得到国家自然科学基金资助. |
| |
| 摘 要： | 本文介绍了知识库更新的基本概念及命题知识库更新的复杂性研究现状．近年来，学者们提出了许多方法进行命题知识库的更新，一类是基于公式的方法；一类是基于模型的方法，但所有这些方法在通常情况下都是难解的．本文讨论基于公式的Ｇｉｎｓｂｅｒｇ更新方法，并给出在公式个数远小于变元个数情况下的一个多项式时间算法．
|
| 关 键 词： | 人工智能 知识库更新 算法复杂性 可满足性问题 命题逻辑 |
| 修稿时间： | 3/3/1995 12:00:00 AM |
THE ALGORITHM AND COMPLEXITY OF PROPOSITIONAL KNOWLEDGE BASE REVISION |
| |
| Tao Xuehong,Sun Wei and Ma Shaohan.THE ALGORITHM AND COMPLEXITY OF PROPOSITIONAL KNOWLEDGE BASE REVISION[J].Journal of Software,1996,7(5):300-305. |
| |
| Authors: | Tao Xuehong Sun Wei and Ma Shaohan |
| |
| Affiliation: | Department of COmputer Science Shandong University Ji'nan 250100 |
| |
| 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. |
| |
| Keywords: | Artificial intelligence knowledge base revision algorithmic complexity SAT problem propositional logic |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
