摘要： 以无基集为基础，结合最大无基集的定义，提出一个多项式时间算法。算法给定一个逻辑程序P和它的一个解释I，求得一个作用在P和I上单调算子的最小不动点，并将该最小不动点中的元素从逻辑程序P的Herbrand基中删去得到一个集合A，集合A即为关于I的最大无基集。实验结果证明了该算法的正确性及复杂性。

关键词: 逻辑程序, 良基模型, 最大无基集, 多项式

Abstract: Based on the definitions of the unfounded set and the greatest unfounded set, it proposes a polynomial time algorithm. In the algorithm, a logic program P and one of its interpretation I are given. It evaluates the least fixed point of a monotone operator with respect to P and I, and then removes the elements in the least fixed point from the Herbrand base of P and get a set A. The set A is the greatest unfounded set with respect to I. It proves the correctness of the algorithm and analyzs its complexity.

Key words: logic program, well-founded model, the greatest unfounded set, polynomial

中图分类号: 

• N311.52