Revisiting the Lexicographic Ordering Constraint

Abstract

We present a global consistency algorithm for the lexicographic ordering constraint on two vectors of n variables. The algorithm maintains arcconsistency, 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.