一类命题知识库的并行更新算法

A PARALLEL PROPOSITIONAL KNOWLEDGE BASE REVISION ALGORITHM

本文介绍了知识库更新的基本概念及命题知识库更新的复杂性研究现状．近年来，提出了许多方法进行命题知识库的更新，一类是基于公式的方法，一类是基于模型的方法，但所有这些方法在通常情况下都是难解的．本文结合实际应用，提出了一种特殊情况下的多项式时间更新方法，并在ＣＲＥＷＰＲＡＭ上给出了相应的并行算法．

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 reserchers,some are formula-based methods and the others are modelbased methods,but all methods are intractable in the general case. For practical application,this paper presents a polynomial revision method in special case,and gives its corresponding parallel algorithm on CREW PRAM.