Revisiting the Lexicographic Ordering Constraint
Revisiting the Lexicographic Ordering Constraint
复制标题
重新审视词典排序约束
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Nicolas Beldiceanu
中科院分区：
文献类型：
--
作者：
M. Carlsson;Nicolas Beldiceanu
给出了一种全局一致性算法
We present a global consistency algorithm for the
lexicographic ordering constraint on two vectors of $n$ variables.
The algorithm maintains arc-consistency, runs in $O(n)$ time on
posting plus amortized $O(1)$ time per propagation event, and detects
entailment or rewrites itself to a simpler constraint whenever
possible. The algorithm was derived from a finite automaton operating
on a string which captures the relationship between each variable pair
of the two vectors.