Complete Propagation Rules for Lexicographic Order Constraints over Arbitrary Domains
Complete Propagation Rules for Lexicographic Order Constraints over Arbitrary Domains
复制标题
任意域上词典顺序约束的完整传播规则
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Thom W. Frühwirth
中科院分区：
文献类型：
--
作者：
Thom W. Frühwirth
我们在约束处理规则（CHR）语言中给出了字典顺序全局约束的有效可执行规范。与以前的方法相比，该实现简短而简洁，并且没有放弃众所周知的最坏情况时间复杂度。 CHR 本质上是增量和并发的。它被证明是正确的和汇合的。它独立于底层约束系统，因此不限于有限域。我们找到了问题的直接递归分解。我们还展示了约束传播的完整性，即约束的所有可能的逻辑结果都是由实现生成的。最后，我们报告了一些实际的实施实验。
We give an efficiently executable specification of the global constraint of lexicographic order in the Constraint Handling Rules (CHR) language. In contrast to previous approaches, the implementation is short and concise without giving up on the best known worst case time complexity. It is incremental and concurrent by nature of CHR. It is provably correct and confluent. It is independent of the underlying constraint system, and therefore not restricted to finite domains. We have found a direct recursive decomposition of the problem. We also show completeness of constraint propagation, i.e. that all possible logical consequences of the constraint are generated by the implementation. Finally, we report about some practical implementation experiments.