消除子句冗余的算法及复杂性

AN ALGORITHM OF REMOVING REDUNDANCY FROM CLAUSE AND ITS COMPLEXITY

本文讨论了知识子句表示的冗余消除，着重讨论了子句中冗余文字消除的情况。压缩是消除子句中文字冗余的一种重要类型，除对这种类型的问题的可判定性以及复杂性结果进行讨论外，本文还给出了压缩问题的一个子问题的多项式算法。

This paper deals with the problem of removing redundancy from a given clause, and discusses the case of redundant literals elimination in a clause. Condensing is one important type of redundancy elimination. We first consider the decidability and complexity of this problem, and then gives a polynomial algorithm of its sub-problem.