A Substitution Operation for Constraints

In order to reduce the search space in finite constraint satisfaction problems, a number of different preprocessing schemes have been proposed. This paper introduces a `substitution' operation for constraints. This new operation generalizes both the idea of enforcing consistency and the notion of label substitution introduced by Freuder. We show that the constraints in a problem may be replaced by substitutable subsets in order to simplify the problem without affecting the existence of a solution. Furthermore, we show how substitutability may be established locally, by considering only a subproblem of the complete problem. 1 Introduction The finite constraint satisfaction problem (or consistent labeling problem) is known to be NP-complete [7]. Such problems may always be solved by an exhaustive search strategy, but this is generally very inefficient. The search space may be reduced by enforcing some level of `consistency' [5] in the problem. This involves strengthening the given cons..