Change search
ReferencesLink to record
Permanent link

Direct link
Revisiting the Lexicographic Ordering Constraint
Number of Authors: 2
2002 (English)Report (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 2002, 1. , 13 p.
SICS Technical Report, ISSN 1100-3154 ; 2002:17
Keyword [en]
Constraint Programming, Global Constraints, Lexicographic Ordering, Symmetry
National Category
Computer and Information Science
URN: urn:nbn:se:ri:diva-14179OAI: diva2:1035467
Available from: 2016-10-13 Created: 2016-10-13

Open Access in DiVA

fulltext(148 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 148 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link