Local Propagation as a Constraint Satisfaction Technique

Motivated by the problem of programming multiprocessors, we study constraint satisfaction as a paradigm on which practical, executable, programming languages can be based. Others have described constraint-based languages, but little analysis of constraint satisfaction heuristics seems to have been done. The contributions of this paper are twofold. First, we examine the complexity of the constraint satisfaction problem. Second, and most important, a formalization of a local propagation heuristic that simplifies one used earlier by Steele [12] is described