一个在Horn子句中求解极大缩减的算法

• 作者: 李未 罗杰
• 来源期刊: 中国科学（信息科学）
• 关键词: 极大缩减 极小不协调集合 极小减集 Horn子句
• 年，卷（期）: 2011,（2）
• 所属期刊栏目: 计算机科学与技术
• 页码范围: 129-143
• 页数: 15页
• 语种: 中文

摘要

在信念修正理论中,一个核心问题是求解一个公式集合关于事实集合的所有极大协调子集,即极大缩减.本文尝试从算法的角度来解决这一问题,研究在Horn子句中求解所有极大缩减的算法,首先,本文指出并证明了公式集合和事实集合并集的极小不协调子集与公式集合关于事实集合的极大缩减之间的转化关系.其次,给出并证明了Horn子句集合极小不协调的一个必要条件.然后,基于上述两个结论,本文提出了一个在Horn子句中枚举公式集合和事实集合并集的极小不协调子集的交互式算法和一个通过这些极小不协调子集计算所有极大缩减的算法.最后,综合这两个算法,提出了一个在Horn子句中求解所有极大缩减的交互式算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李未	北京航空航天大学计算机学院软件开发环境国家重点实验室	23	113	7.0	10.0
2	罗杰	北京航空航天大学计算机学院软件开发环境国家重点实验室	3	0	0.0	0.0