Creignou, N. and Hermann, M. and Krokhin, A. and Salzer, G. (2008) 'Complexity of clausal constraints over chains.', Theory of computing systems., 42 (2). pp. 239-255.
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≥d and x≤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.
|Keywords:||Constraint satisfaction problems, Complexity, Finite totally ordered domains, Inequalities, Clausal patterns, Dichotomy theorem.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/s00224-007-9003-z|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||February 2008|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|