Thu Sep 3 13:47:40 CEST 2009
Context: I'm looking at the jump from data flow programming -> local
consistency rules. More specifically, in my application at hand,
are local constraints enough? (as opposed to global constraints like
simultaneous sets of equations) If so, then (staged) constraint
propagation is a good solution.
Let's look at the ``trivial constraint language'' described in chapter
2 of . It focusses on local propagation only. Apart from simple
arithmetic constraints it is useful for allowing constraints that
can't be directionalized fully, i.e. writen in terms of inequalities
like m = max(a,b)
The remaining chapters then talk about removing some of the
deficiencies: data types, abstraction mechanisms, multiple use
(tracking changing data), global issues and dependencies of
constraints (why is there a contradiction?).
In , a constraint satisfaction problem is defined as a set of
variables, a set of domains, and a set of constraints. Variables and
domains are associated: the domain of a variable contains all values
the variable can take. A constraint is composed of a sequence of
variables, called its scope, and a set of their evaluations, which are
the evaluations satisfying the constraint.