Polynomial constraints over finite domains are expressed as equalities, inequalities, and disequalities of polynomials with integer coefficients whose variables take values from finite subsets of the integers. They are an interesting type of constraints that can be used to model many combinatorial problems over the integers. Sign consistency is a type of local consistency proposed specifically to support reasoning on polynomial constraints over finite domains. Sign consistency is parameterized in terms of a bounding function that is used to extract relevant information from a constraint when its variables are restricted to take values from a finite box. Known results from the literature on interval arithmetic can be readily used to propose a simple bounding function to support sign consistency. Preliminary experimental results show that the proposed bounding function is a promising candidate to effectively reason on polynomial constraints over finite domains.
Simple and effective sign consistency using interval arithmetic / Bergenti, F.; Monica, S.. - ELETTRONICO. - 2396:(2019), pp. 89-103. (Intervento presentato al convegno 34th Italian Conference on Computational Logic (CILC 2019) nel 2019).
Simple and effective sign consistency using interval arithmetic
Bergenti F.
;Monica S.
2019-01-01
Abstract
Polynomial constraints over finite domains are expressed as equalities, inequalities, and disequalities of polynomials with integer coefficients whose variables take values from finite subsets of the integers. They are an interesting type of constraints that can be used to model many combinatorial problems over the integers. Sign consistency is a type of local consistency proposed specifically to support reasoning on polynomial constraints over finite domains. Sign consistency is parameterized in terms of a bounding function that is used to extract relevant information from a constraint when its variables are restricted to take values from a finite box. Known results from the literature on interval arithmetic can be readily used to propose a simple bounding function to support sign consistency. Preliminary experimental results show that the proposed bounding function is a promising candidate to effectively reason on polynomial constraints over finite domains.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.