Constraint inference

In <a href="/facts/Constraint_satisfaction/PXI74p1T">constraint satisfaction</a>, constraint inference is a relationship between constraints and their consequences. A set of constraints 
 
 
 
 D
 
 
 {\displaystyle D}
 
 entails a constraint 
 
 
 
 C
 
 
 {\displaystyle C}
 
 if every solution to 
 
 
 
 D
 
 
 {\displaystyle D}
 
 is also a solution to 
 
 
 
 C
 
 
 {\displaystyle C}
 
. In other words, if 
 
 
 
 V
 
 
 {\displaystyle V}
 
 is a valuation of the variables in the scopes of the constraints in 
 
 
 
 D
 
 
 {\displaystyle D}
 
 and all constraints in 
 
 
 
 D
 
 
 {\displaystyle D}
 
 are satisfied by 
 
 
 
 V
 
 
 {\displaystyle V}
 
, then 
 
 
 
 V
 
 
 {\displaystyle V}
 
 also satisfies the constraint 
 
 
 
 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 
 
 
 
 (
 (
 x
 ,
 y
 )
 ,
 R
 )
 
 
 {\displaystyle ((x,y),R)}
 
 and 
 
 
 
 (
 (
 y
 ,
 z
 )
 ,
 S
 )
 
 
 {\displaystyle ((y,z),S)}
 
 with a common variable. The composition of such two constraints is the constraint 
 
 
 
 (
 (
 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 
 
 
 
 y
 
 
 {\displaystyle y}
 
 such that the evaluation of these three variables satisfies the two original constraints 
 
 
 
 (
 (
 x
 ,
 y
 )
 ,
 R
 )
 
 
 {\displaystyle ((x,y),R)}
 
 and 
 
 
 
 (
 (
 y
 ,
 z
 )
 ,
 S
 )
 
 
 {\displaystyle ((y,z),S)}
 
.
Constraint projection restricts the effects of a constraint to some of its variables. Given a constraint 
 
 
 
 (
 t
 ,
 R
 )
 
 
 {\displaystyle (t,R)}
 
 its projection to a subset 
 
 
 
 
 t
 ′
 
 
 
 {\displaystyle t'}
 
 of its variables is the constraint 
 
 
 
 (
 
 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 
 
 
 
 (
 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 
 
 
 
 
 C
 
 1
 
 
 ,
 …
 ,
 
 C
 
 m
 
 
 
 
 {\displaystyle C_{1},\ldots ,C_{m}}
 
 and a list 
 
 
 
 A
 
 
 {\displaystyle A}
 
 of their variables, the extended composition of them is the constraint 
 
 
 
 (
 A
 ,
 R
 )
 
 
 {\displaystyle (A,R)}
 
 where an evaluation of 
 
 
 
 A
 
 
 {\displaystyle A}
 
 satisfies this constraint if it can be extended to the other variables so that 
 
 
 
 
 C
 
 1
 
 
 ,
 …
 ,
 
 C
 
 m
 
 
 
 
 {\displaystyle C_{1},\ldots ,C_{m}}
 
 are all satisfied.

Constraint inference open-in-new

Constraint inference