[<<][compsci][>>][..]

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

[Reply][About]

[<<][compsci][>>][..]