Thu Sep 3 13:47:40 CEST 2009

Local consistency

Context: I'm looking at the jump from data flow programming -> local
consistency rules[1].  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 [2].  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 [1], 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.

[1] http://en.wikipedia.org/wiki/Local_consistency
[2] http://www.ai.mit.edu/publications/pubsDB/pubs.doit?search=AITR-595