Hyper-arc consistency of polynomial constraints over finite domains using the modified Bernstein form |
| |
Authors: | Federico Bergenti Stefania Monica |
| |
Affiliation: | 1.Dipartimento di Scienze Matematiche, Fisiche e Informatiche,Università degli Studi di Parma,Parma,Italy |
| |
Abstract: | This paper describes an algorithm to enforce hyper-arc consistency of polynomial constraints defined over finite domains. First, the paper describes the language of so called polynomial constraints over finite domains, and it introduces a canonical form for such constraints. Then, the canonical form is used to transform the problem of testing the satisfiability of a constraint in a box into the problem of studying the sign of a related polynomial function in the same box, a problem which is effectively solved by using the modified Bernstein form of polynomials. The modified Bernstein form of polynomials is briefly discussed, and the proposed hyper-arc consistency algorithm is finally detailed. The proposed algorithm is a subdivision procedure which, starting from an initial approximation of the domains of variables, removes values from domains to enforce hyper-arc consistency. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|