Generation of Implied Constraints for Automaton-Induced Decompositions
Generation of Implied Constraints for Automaton-Induced Decompositions
复制标题
自动机引发分解的隐含约束的生成
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
J. Pearson
中科院分区：
文献类型：
--
作者：
María Andreína Francisco Rodríguez;P. Flener;J. Pearson
自动机，可能带有计数器，允许以简单和高级的方式表达许多约束。自动机将分解归纳为已实现的约束的合取。对于由具有多于一个状态或计数器的计数器自动机诱导的分解，一般不保持广义圆弧一致性。为了改进自动机诱导的约束分解的传播，我们使用自动化工具从与给定自动机相对应的约束检查器中获得循环不变量。这些循环不变量对应于隐含的约束，可以添加到分解中。我们考虑了两个全局约束，并推导出隐含约束以改善传播，甚至达到保持广义圆弧一致性的程度。
Automata, possibly with counters, allow many constraints to be expressed in a simple and high-level way. An automaton induces a decomposition into a conjunction of already implemented constraints. Generalised arc consistency is not generally maintained on decompositions induced by counter automata with more than one state or counter. To improve propagation of automaton-induced constraint decompositions, we use automated tools to derive loop invariants from the constraint checker corresponding to the given automaton. These loop invariants correspond to implied constraints, which can be added to the decomposition. We consider two global constraints and derive implied constraints to improve propagation even to the point of maintaining generalised arc consistency.