Details:
Title  Representing and solving finitedomain constraint problems using systems of polynomials.  Author(s)  Martin J. Green, Peter Jeavons, Christopher Jefferson, Marc R. C. van Dongen  Type  Article in Journal  Abstract  In this paper we investigate the use of a system of multivariate polynomials to represent the restrictions imposed by a collection of constraints. One advantage of using polynomials to represent constraints is that it allows many different forms of constraints to be treated in a uniform way. Systems of polynomials have been widely studied, and a number of general techniques have been developed, including algorithms that generate an equivalent system with certain desirable properties, called a Gröbner Basis. General algorithms to compute a Gröbner Basis have doubly exponential complexity, but we observe that for the systems we use to describe constraint problems over finite domains a Gröbner Basis can be computed more efficiently than this. We also describe a family of algorithms, related to the calculation of Gröbner Bases, that can be used on any system of polynomials to compute an equivalent system in polynomial time. We show that these modified algorithms can simulate the effect of the localconsistency algorithms used in constraint programming and hence solve certain broad classes of constraint problems in polynomial time. Finally we discuss the use of adaptive consistency techniques for systems of polynomials.  Keywords  Constraint satisfaction, Groebner basis, Consistency  ISSN  10122443; 15737470/e 
URL 
Constraint satisfaction Groebner basis Consistency 
Language  English  Journal  Ann. Math. Artif. Intell.  Volume  67  Number  34  Pages  359382  Publisher  Springer International Publishing, Cham  Year  2013  Edition  0  Translation 
No  Refereed 
No 
