Constraint inference
In constraint satisfaction, constraint inference is a relationship between constraints and their consequences. A set of constraints [math]\displaystyle{ D }[/math] entails a constraint [math]\displaystyle{ C }[/math] if every solution to [math]\displaystyle{ D }[/math] is also a solution to [math]\displaystyle{ C }[/math]. In other words, if [math]\displaystyle{ V }[/math] is a valuation of the variables in the scopes of the constraints in [math]\displaystyle{ D }[/math] and all constraints in [math]\displaystyle{ D }[/math] are satisfied by [math]\displaystyle{ V }[/math], then [math]\displaystyle{ V }[/math] also satisfies the constraint [math]\displaystyle{ C }[/math]. Some operations on constraints produce a new constraint that is a consequence of them. Constraint composition operates on a pair of binary constraints [math]\displaystyle{ ((x,y),R) }[/math] and [math]\displaystyle{ ((y,z),S) }[/math] with a common variable. The composition of such two constraints is the constraint [math]\displaystyle{ ((x,z),Q) }[/math] that is satisfied by every evaluation of the two non-shared variables for which there exists a value of the shared variable [math]\displaystyle{ y }[/math] such that the evaluation of these three variables satisfies the two original constraints [math]\displaystyle{ ((x,y),R) }[/math] and [math]\displaystyle{ ((y,z),S) }[/math].
Constraint projection restricts the effects of a constraint to some of its variables. Given a constraint [math]\displaystyle{ (t,R) }[/math] its projection to a subset [math]\displaystyle{ t' }[/math] of its variables is the constraint [math]\displaystyle{ (t',R') }[/math] that is satisfied by an evaluation if this evaluation can be extended to the other variables in such a way the original constraint [math]\displaystyle{ (t,R) }[/math] 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 [math]\displaystyle{ C_1,\ldots,C_m }[/math] and a list [math]\displaystyle{ A }[/math] of their variables, the extended composition of them is the constraint [math]\displaystyle{ (A,R) }[/math] where an evaluation of [math]\displaystyle{ A }[/math] satisfies this constraint if it can be extended to the other variables so that [math]\displaystyle{ C_1,\ldots,C_m }[/math] are all satisfied.
See also
References
- Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. http://www.ics.uci.edu/~dechter/books/index.html. 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
 |  |
