Confluence of reduction rules for lexicographic ordering constraints

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The lex leader method for breaking symmetry in CSPs typically produces a large set of lexicographic ordering constraints. Several rules have been proposed to reduce such sets whilst preserving logical equivalence. These reduction rules are not generally confuent: they may reach more than one xpoint, depending on the order of application. These fixpoints vary in size. Smaller sets of lex constraints are desirable so ensuring reduction to a global minimum is essential. We characterise the systems of constraints for which the reduction rules are confluent in terms of a simple feature of the input, and define an algorithm to determine whether a set of lex constraints reduce confuently.
Original languageEnglish
Title of host publication Proceedings of the Eighth International Symposium on Abstraction, Reformulation and Approximation
EditorsVadim Bulitko, Chris Beck
PublisherAAAI Press
Number of pages7
ISBN (Print)978-1-57735-433-8
Publication statusPublished - 2009


Dive into the research topics of 'Confluence of reduction rules for lexicographic ordering constraints'. Together they form a unique fingerprint.

Cite this