Paper Info
Title
Efficient Algorithms for Constraint Description Problems over Finite Totally Ordered Domains: Extended Abstract
Abstract
Given a finite set of vectors over a finite totally ordered do- main, we study the problem of computing a constraint in conjunctive normal form such that the set of solutions for the produced constraint is identical to the original set. We develop an efficient polynomial-time algorithm for the general case, followed by specific polynomial-time al- gorithms producing Horn, dual Horn, and bijunctive constraints for sets of vectors closed under the operations of conjunction, disjunction, and median, respectively. We also consider the affine constraints, analyzing them by means of computer algebra. Our results generalize the work of Dechter and Pearl on relational data, as well as the papers by Hebrard and Zanuttini. They also complete the results of Hahnle et al. on multi- valued logics and Jeavons et al. on the algebraic approach to constraints. We view our work as a step toward a complete complexity classification of constraint satisfaction problems over finite domains.
Year
Venue
Keywords
2004
IJCAR
polynomial time,relational data,computer algebra,conjunctive normal form,total order,constraint satisfaction problem
Field
DocType
Citations 
Constraint satisfaction,Discrete mathematics,Finite set,Abstract interpretation,Computer science,Symbolic computation,Algorithm,Constraint satisfaction problem,Constraint satisfaction dual problem,Conjunctive normal form,Time complexity
Conference
0
PageRank 
References 
Authors
0.34
15
4
Name
Order
Citations
PageRank
Àngel J. Gil1576.21
Miki Hermann238227.84
Gernot Salzer321222.62
Bruno Zanuttini428925.43