This paper shows how the solutions of constraint satisfac-tion problems that involve only polynomial constraints over finite do-mains can be enumerated by computing the values of related polynomial functions at appropriate points. The proposed algorithm first transforms constraints, which are expressed as equalities, inequalities, and disequal-ities of polynomials with integer coefficients and integer variables, into a canonical form that uses only inequalities. Then, starting from a bound-ing box, which is supposed to be known, the algorithm recursively sub-divides the box into disjoint boxes and it records boxes whose elements satisfy all constraints. The subdivision is driven by the study of the sign of polynomial functions over boxes, which is performed by means of a method that uses only the coefficients of polynomials and the values of functions at the corners of boxes.

Satisfaction of polynomial constraints over finite domains using function values / Bergenti, Federico; Monica, Stefania. - 1949:(2017), pp. 262-275. (Intervento presentato al convegno Joint 18th Italian Conference on Theoretical Computer Science and the 32nd Italian Conference on Computational Logic, ICTCS 2017 and CILC 2017 tenutosi a Napoli nel 2017).

### Satisfaction of polynomial constraints over finite domains using function values

#### Abstract

This paper shows how the solutions of constraint satisfac-tion problems that involve only polynomial constraints over finite do-mains can be enumerated by computing the values of related polynomial functions at appropriate points. The proposed algorithm first transforms constraints, which are expressed as equalities, inequalities, and disequal-ities of polynomials with integer coefficients and integer variables, into a canonical form that uses only inequalities. Then, starting from a bound-ing box, which is supposed to be known, the algorithm recursively sub-divides the box into disjoint boxes and it records boxes whose elements satisfy all constraints. The subdivision is driven by the study of the sign of polynomial functions over boxes, which is performed by means of a method that uses only the coefficients of polynomials and the values of functions at the corners of boxes.
##### Scheda breve Scheda completa Scheda completa (DC) 2017
Joint 18th Italian Conference on Theoretical Computer Science and the 32nd Italian Conference on Computational Logic, ICTCS 2017 and CILC 2017
Napoli
2017
1949
262
275
Bergenti, Federico; Monica, Stefania
Satisfaction of polynomial constraints over finite domains using function values / Bergenti, Federico; Monica, Stefania. - 1949:(2017), pp. 262-275. (Intervento presentato al convegno Joint 18th Italian Conference on Theoretical Computer Science and the 32nd Italian Conference on Computational Logic, ICTCS 2017 and CILC 2017 tenutosi a Napoli nel 2017).
File in questo prodotto:
Non ci sono file associati a questo prodotto.
##### Pubblicazioni consigliate I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11380/1207067`
##### Citazioni
• ND
• 5
• ND