A Refinement Operator for Theories
A Refinement Operator for Theories
复制标题
理论精化算子
DOI：
10.1007/3-540-44797-0_1
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Liviu Badea
中科院分区：
文献类型：
--
作者：
Liviu Badea
大多数实现的ILP系统使用子句的细化算子逐个子句构造假设。为了避免这种贪婪覆盖算法所面临的问题，需要更灵活的理论改进算子。在本文中，我们为理论构造了一个语法上单调的、有限的、解完全的改进算子，它消除了某些令人讨厌的冗余（由于子句删除），同时也解决了HYPER的改进算子所面临的局限性（主要是由于在改进过程中保持子句数量不变）。我们还展示了如何在保留弱完备性和有限形式的灵活性的同时消除由于改进操作的交换性而产生的冗余。本文提出的细化算子是构建具有精确理论保证的更高效、更灵活的ilp系统的第一步。
Most implemented ILP systems construct hypotheses clause by clause using a refinement operatorfor clauses. To avoid the problems faced by such greedy covering algorithms, moreflexiblerefinement operatorsfor theoriesare needed. In this paper we construct a syntactically monotonic, finite and solution-complete refinement operator for theories, which eliminates certain annoying redundancies (due to clause deletions), while also addressing the limitations faced by HYPER’s refinement operator (which are mainly due to keeping the number of clauses constant during refinement).We also show how to eliminate the redundancies due to the commutativity of refinement operations while preserving weak completeness as well as a limited form of flexibility. The refinement operator presented in this paper represents a first step towards constructing more efficient andflexibleILP systems with precise theoretical guarantees.