Revisiting the Lexicographic Ordering Constraint

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
ID Code:2266
Deposited By:Vicki Carleson
Deposited On:29 Oct 2007
Last Modified:18 Nov 2009 16:03

Repository Staff Only: item control page