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.

Hyper-arc consistency of polynomial constraints over finite domains using the modified Bernstein form / Bergenti, Federico; Monica, Stefania. - In: ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE. - ISSN 1012-2443. - 80:2(2017), pp. 131-151. [10.1007/s10472-017-9544-z]

### Hyper-arc consistency of polynomial constraints over finite domains using the modified Bernstein form

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC) 2017
80
2
131
151
Hyper-arc consistency of polynomial constraints over finite domains using the modified Bernstein form / Bergenti, Federico; Monica, Stefania. - In: ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE. - ISSN 1012-2443. - 80:2(2017), pp. 131-151. [10.1007/s10472-017-9544-z]
Bergenti, Federico; Monica, Stefania
File in questo prodotto:
File
AM&AI 2017.pdf

Accesso riservato

Dimensione 1.02 MB Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11380/1207047`
• ND
• 6
• 3