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.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