### Functional and Piecewise Functional Constraints

The specialized AC algorithms for the hidden variable and the dual encoding that we will describe in Sections 3 and 4 exploit structural properties of the encodings. As we will explain in detail later, the binary constraints in the hidden variable encoding are one-way functional, while the binary constraints in the dual encoding are piecewise functional. We now define these concepts.

Definition 2.2   A binary constraint , where , is functional with respect to and iff for all (resp. ) there exists at most one value (resp. ) such that is a support of in (resp. is a support of ).

An example of a functional constraint is . A binary constraint is one-way functional if the functionality property holds with respect to only one of the variables involved in the constraint.

Informally, a piecewise functional constraint over variables , is a constraint where the domains of and can be partitioned into groups such that each group of is supported by at most one group of , and vice versa. To give a formal definition, we first define the concept of a piecewise decomposition.

Definition 2.3   [Van Hentenryck, Deville, TengVan Hentenryck et al.1992] Let be a binary constraint with . The partitions of and of are a piecewise decomposition of and with respect to iff for all ,, the following property holds: either for all , , , or for all , , .

Definition 2.4   [Van Hentenryck, Deville, TengVan Hentenryck et al.1992] A binary constraint , where , is piecewise functional with respect to and iff there exists a piecewise decomposition of and of with respect to such that for all (resp. ), there exists at most one (resp. ), such that for all , .

Example of piecewise functional constraints are the modulo ( MOD = ) and integer division ( DIV = ) constraints.

Nikolaos Samaras 2005-11-09