Carlsson, Mats and Beldiceanu, Nicolas (2002) Revisiting the Lexicographic Ordering Constraint. [SICS Report]
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.
|Item Type:||SICS Report|
|Uncontrolled Keywords:||Constraint Programming, Global Constraints, Lexicographic Ordering, Symmetry|
|Deposited By:||Vicki Carleson|
|Deposited On:||29 Oct 2007|
|Last Modified:||18 Nov 2009 16:03|
Repository Staff Only: item control page