| 一个在Horn子句中求解极大缩减的算法 |
| |
| 引用本文： | 罗杰,李未. 一个在Horn子句中求解极大缩减的算法[J]. 中国科学:信息科学, 2011, 0(2) |
| |
| 作者姓名： | 罗杰 李未 |
| |
| 作者单位： | 北京航空航天大学计算机学院软件开发环境国家重点实验室; |
| |
| 基金项目： | 国家重点基础研究发展计划(批准号:2005CB321901); 国家高技术研究发展计划(批准号:2007AA01Z146); 软件开发环境国家重点实验室自主课题(批准号:SKLSDE-2008ZX-01)资助项目 |
| |
| 摘 要： | 在信念修正理论中,一个核心问题是求解一个公式集合关于事实集合的所有极大协调子集,即极大缩减.本文尝试从算法的角度来解决这一问题,研究在Horn子句中求解所有极大缩减的算法.首先,本文指出并证明了公式集合和事实集合并集的极小不协调子集与公式集合关于事实集合的极大缩减之间的转化关系.其次,给出并证明了Horn子句集合极小不协调的一个必要条件.然后,基于上述两个结论,本文提出了一个在Horn子句中枚举公式集合和事实集合并集的极小不协调子集的交互式算法和一个通过这些极小不协调子集计算所有极大缩减的算法.最后,综合这两个算法,提出了一个在Horn子句中求解所有极大缩减的交互式算法.
|
| 关 键 词： | 极大缩减 极小不协调集合 极小减集 Horn子句 |
An algorithm to compute maximal contractions for Horn clauses |
| |
| LUO Jie , LI Wei State Key Laboratory of Software Development Environment,School of Computer Science , Technology,Beihang University,Beijing ,China. An algorithm to compute maximal contractions for Horn clauses[J]. Scientia Sinica Informationis, 2011, 0(2) |
| |
| Authors: | LUO Jie & LI Wei State Key Laboratory of Software Development Environment School of Computer Science Technology Beihang University Beijing China |
| |
| Affiliation: | LUO Jie & LI Wei State Key Laboratory of Software Development Environment,School of Computer Science and Technology,Beihang University,Beijing 100191,China |
| |
| Abstract: | In the theory of belief revision,the computation of all maximal subsets(maximal contractions) of a formula set with respect to a set of facts is one of the key problems.In this paper,we try to solve this problem by studying the algorithm to compute all maximal contractions for Horn clauses.First,we point out and prove the conversion relationship between minimal inconsistent subsets of union of the formula set and the set of facts and maximal contractions of the formula set with respect to the set of facts.S... |
| |
| Keywords: | maximal contraction minimal inconsistent set minimal subtraction Horn clause |
| 本文献已被 CNKI 等数据库收录！ |
|
