Foundations Of Cognitive Science

Constraint Propagation

The central idea underlying natural computation is constraint propagation (e.g., Pylyshyn, 2003).  Imagine a set of locations to which labels can be assigned, where each label is a possible property that is present at a location.  Underdetermination exists when more than one label is possible at various locations.  However, constraints can be applied to remove these ambiguities.  Imagine that if some label x is assigned to one location then this prevents some other label y from being assigned to a neighboring location, because the labels are mutually inconsistent.  Say that there is good evidence to assign label x to the first location.  Once this is done, a constraint can propagate outwards from this location to its neighbors, removing label y as a possibility for them, and reducing ambiguity.  A typical algorithm for performing constraint propagation is called relaxation labeling; connectionist networks are also well-suited to propagate constraints to solve problems of underdetermination.


  1. Pylyshyn, Z. W. (2003). Seeing and Visualizing: It's Not What You Think. Cambridge, Mass.: MIT Press.

(Added March 2011)