go-v.orgcodex
Menu
Page tools

codex · Philosophy

Constraint inference

In constraint satisfaction, constraint inference is a relationship between constraints and their consequences. A set of constraints D entails a constraint C if every solution to D is also a solution to C. In other words, if V is a valuation of the variables in the scopes of the constraints in D and all constraints in D are satisfied by V, then V also satisfies the constraint 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) and ((y,z),S) with a common variable.

The composition of such two constraints is the constraint ((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 such that the evaluation of these three variables satisfies the two original constraints ((x,y),R) and ((y,z),S). Constraint projection restricts the effects of a constraint to some of its variables. Given a constraint (t,R) its projection to a subset t′ of its variables is the constraint (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) 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 C1,…,Cm and a list A of their variables, the extended composition of them is the constraint (A,R) where an evaluation of A satisfies this constraint if it can be extended to the other variables so that C1,…,Cm are all satisfied.

Wikipedia contributors, "Constraint inference", Wikipedia, revision 1120919123, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex