Constraint inference

In constraint satisfaction, constraint inference is a relationship between constraints and their consequences. A set of constraints ${\displaystyle D}${\displaystyle D} entails a constraint ${\displaystyle C}${\displaystyle C} if every solution to ${\displaystyle D}${\displaystyle D} is also a solution to ${\displaystyle C}${\displaystyle C}. In other words, if ${\displaystyle V}${\displaystyle V} is a valuation of the variables in the scopes of the constraints in ${\displaystyle D}${\displaystyle D} and all constraints in ${\displaystyle D}${\displaystyle D} are satisfied by ${\displaystyle V}${\displaystyle V}, then ${\displaystyle V}${\displaystyle V} also satisfies the constraint ${\displaystyle C}${\displaystyle C}.

Some operations on constraints produce a new constraint that is a consequence of them. Constraint composition operates on a pair of binary constraints ${\displaystyle ((x,y),R)}${\displaystyle ((x,y),R)} and ${\displaystyle ((y,z),S)}${\displaystyle ((y,z),S)} with a common variable. The composition of such two constraints is the constraint ${\displaystyle ((x,z),Q)}${\displaystyle ((x,z),Q)} that is satisfied by every evaluation of the two non-shared variables for which there exists a value of the shared variable ${\displaystyle y}${\displaystyle y} such that the evaluation of these three variables satisfies the two original constraints ${\displaystyle ((x,y),R)}${\displaystyle ((x,y),R)} and ${\displaystyle ((y,z),S)}${\displaystyle ((y,z),S)}.

Constraint projection restricts the effects of a constraint to some of its variables. Given a constraint ${\displaystyle (t,R)}${\displaystyle (t,R)} its projection to a subset ${\displaystyle t'}${\displaystyle t'} of its variables is the constraint ${\displaystyle (t',R')}${\displaystyle (t',R')} that is satisfied by an evaluation if this evaluation can be extended to the other variables in such a way the original constraint ${\displaystyle (t,R)}${\displaystyle (t,R)} is satisfied.

Extended composition is similar in principle to composition, but allows for an arbitrary number of possibly non-binary constraints; the generated constraint is on an arbitrary subset of the variables of the original constraints. Given constraints ${\displaystyle C_{1},\ldots ,C_{m}}${\displaystyle C_{1},\ldots ,C_{m}} and a list ${\displaystyle A}${\displaystyle A} of their variables, the extended composition of them is the constraint ${\displaystyle (A,R)}${\displaystyle (A,R)} where an evaluation of ${\displaystyle A}${\displaystyle A} satisfies this constraint if it can be extended to the other variables so that ${\displaystyle C_{1},\ldots ,C_{m}}${\displaystyle C_{1},\ldots ,C_{m}} are all satisfied.

• Constraint satisfaction problem

• Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 1-55860-890-7
• Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press. ISBN 0-521-82583-0
• Marriott, Kim; Peter J. Stuckey (1998). Programming with constraints: An introduction. MIT Press. ISBN 0-262-13341-5

• Constraint programming
• Inference
• Applied mathematics stubs

• All stub articles