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|
|Record Created:||15 Dec 2009 12:05|
|Last Modified:||05 Jan 2010 10:51|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|