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. - ELETTRONICO. - 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 nel 2017.

Satisfaction of polynomial constraints over finite domains using function values

Bergenti, Federico;Monica, Stefania
2017

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.
Satisfaction of polynomial constraints over finite domains using function values / Bergenti, Federico; Monica, Stefania. - ELETTRONICO. - 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 nel 2017.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2838732
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact