Propagation Completeness of Reactive Constraints
Propagation Completeness of Reactive Constraints
复制标题
反应性约束的传播完整性
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Michael J. Maher
中科院分区：
文献类型：
--
作者：
Michael J. Maher
我们开发了一个框架来解决反应性约束的正确性和传播的及时性问题--通过约束传播实现的全局约束或用户定义的约束。引入传播完备性的概念来捕捉约束传播的时效性。给出了圆弧相容的一种推广形式，统一了文献中的许多局部相容条件。我们证明了当传播停顿时，无功约束的传播完全实现实现了这种弧一致性。最后，我们使用该框架声明并证明了一个不可能的结果：CHR不能实现具有期望的及时约束传播程度的公共关系。
We develop a framework for addressing correctness and timeliness-of-propagation issues for reactive constraints - global constraints or user-defined constraints that are implemented through constraint propagation. The notion of propagation completeness is introduced to capture timeliness of constraint propagation. A generalized form of arc-consistency is formulated which unifies many local consistency conditions in the literature. We show that propagation complete implementations of reactive constraints achieve this arc-consistency when propagation quiesces. Finally, we use the framework to state and prove an impossibility result: that CHR cannot implement a common relation with a desirable degree of timely constraint propagation.