Decomposable constraints

Many constraint satisfaction problems can be naturally and efficiently mode lled using non-binary constraints like the "all-different" and "global card inality" constraints. Certain classes of these nonbinary constraints are "n etwork decomposable" as they can be represented by binary constraints on th e same set of variables. We compare theoretically the levels of consistency which are achieved on non-binary constraints to those achieved on their bi nary decomposition. We present many results about the level of consistency achieved by the forward checking algorithm and its various generalizations to non-binary constraints. We also compare the level of consistency achieve d by arc-consistency and its generalization to non-binary constraints, and identify special cases of non-binary decomposable constraints where weaker or stronger conditions, than in the general case, hold. We also analyze the cost, in consistency checks, required to achieve certain levels of consist ency, and we present experimental results on benchmark domains that demonst rate the practical usefulness of our theoretical analysis. (C) 2000 Elsevie r Science B.V. All rights reserved.