2.1.8. Property view

If we want to reason about constraints we need to know their properties. Examples of properties of a constraint with respect to one of its arguments are:

• A constraint $c\left(\langle x_1,x_2,\cdots ,x_n\rangle \right)$ is contractible if each ground satisfied instance $c\left(\langle {\mathrm{𝑣𝑎𝑙}}_1,{\mathrm{𝑣𝑎𝑙}}_2,\cdots ,{\mathrm{𝑣𝑎𝑙}}_n\rangle \right)$ is still satisfied if we remove any of its ${\mathrm{𝑣𝑎𝑙}}_i$ ($1\le i\le n$).

• A constraint $c\left(\langle x_1,x_2,\cdots ,x_n\rangle \right)$ is extensible if each ground satisfied instance $c\left(\langle {\mathrm{𝑣𝑎𝑙}}_1,{\mathrm{𝑣𝑎𝑙}}_2,\cdots ,{\mathrm{𝑣𝑎𝑙}}_n\rangle \right)$ is still satisfied if we insert any value into the sequence ${\mathrm{𝑣𝑎𝑙}}_1,{\mathrm{𝑣𝑎𝑙}}_2,\cdots ,{\mathrm{𝑣𝑎𝑙}}_n$.

Examples of properties of a constraint with respect to another constraint are:

• The fact that a constraint implies another constraint under the assumption that both constraints have exactly the same arguments.

• The fact that if a constraint holds then another constraint does not hold, under the assumption that both constraints have exactly the same arguments.

Regarding the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint we have:

• It is contractible since removing a value from a ground satisfied instance leaves the remaining constraint satisfied.

• It is not extensible since adding a value into a ground satisfied instance may not necessarily lead to a satisfied constraint.

• The $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint is implied by more specific constraints, such as the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}\_\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$ constraint, which in addition forces all used values to be consecutive.

We now illustrate how to use such knowledge as a method for trying to check that a given conjunction of identical constraints, i.e. constraints with the same name, is implied by another conjunction of also identical constraints. This subproblem originates from learning models where we want to keep only the more general conjunctions of identical constraints. Consider the conjunction ${𝒞}_1$

where $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}\_\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$ forces variables to take consecutive distinct values, and the conjunction ${𝒞}_2$

Conjunction ${𝒞}_1$ implies conjunction ${𝒞}_2$ since every constraint of ${𝒞}_2$ is implied by at least one constraint of ${𝒞}_1$. For instance, $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\langle v_1,v_2\rangle \right)$ is implied by $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}\_\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$$\left(\langle v_1,v_2,v_3,v_4\rangle \right)$ since:

• $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}\_\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$$\left(\langle v_1,v_2,v_3,v_4\rangle \right)\Rightarrow$ $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\langle v_1,v_2,v_3,v_4\rangle \right)$.

• $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\langle v_1,v_2,v_3,v_4\rangle \right)$ is contractible, it implies $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\langle v_1,v_2\rangle \right)$.