|- Up -|
This intuitive way, presented above, of capturing partial information about an assignment can be formally presented as a logical system of Basic Constraints. Its abstract syntax is given by:
It is equipped with the following inference rules.
Of course, after saturation with the above rules, for each variable there is always a most specific approximation of its assignment. For an integer variable , this is the smallest such that . For a set variable there is a largest lower bound and a smallest upper bound . In practice, these most specific basic constraints are the only ones that the system needs to represent (all others can be derived by weakening).
A constraint programming system contains a constraint store which is the (saturated) set of basic constraints representing the partial information currently known about the assignment.
We say that a variable is determined when its assignment has been decided. For an integer variable this happens when its domain becomes a singleton. For a set variable this happens when its lower bound becomes equal to its upper bound.
|- Up -|