计算机工程 ›› 2011, Vol. 37 ›› Issue (11): 181-183.doi: 10.3969/j.issn.1000-3428.2011.11.062

• 人工智能及识别技术 • 上一篇    下一篇

计算最大无基集的多项式时间算法

魏昆鹏1,王以松2   

  1. (贵州大学计算机科学与信息学院,贵阳 550025)
  • 收稿日期:2010-12-25 出版日期:2011-06-05 发布日期:2011-06-05
  • 作者简介:魏昆鹏(1985-),男,硕士研究生,主研方向:人工智能;王以松,副教授
  • 基金项目:
    贵州省自然科学基金资助项目(黔科合J字[2008]2119号);贵州省教育厅自然科学基金资助项目((2008)011)

Polynomial Time Algorithm for Calculating the Greatest Unfounded Set

WEI Kun-peng  1, WANG Yi-song  2   

  1. (College of Computer Science & Information, Guizhou University, Guiyang 550025, China)
  • Received:2010-12-25 Online:2011-06-05 Published:2011-06-05

摘要: 以无基集为基础,结合最大无基集的定义,提出一个多项式时间算法。算法给定一个逻辑程序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

中图分类号: