We investigate the complexity of the satisfiability problem of
constraints over finite totally ordered domains. In our context, a
clausal constraint is a disjunction of inequalities of the form $x
\geq d$ and $x \leq d$.
We classify the complexity of constraints based on clausal patterns.
A pattern abstracts away from variables and contains only
information about the domain elements and the type of inequalities
occurring in a constraint. Every finite set of patterns gives rise
to a (clausal) constraint satisfaction problem in which all
constraints in instances must have an allowed pattern. We prove that
every such problem is either polynomially decidable or
NP-complete, and give a polynomial-time algorithm for recognizing
the tractable cases. Some of these tractable cases are new and have
not been previously identified in the literature.
(this work was done in cooperation with Nadia Creignou, Andrei Krokhin, and Gernot Salzer)