
## 2.3 Other Extended Forms Of Interchangeability

Other extended forms that were initially proposed are: meta-interchangeability, dynamic interchangeability, and functional interchangeability.

Meta-interchangeability (MI) [Freuder, 1991] By grouping variables into
'meta-variables', or values into 'meta-values', we can introduce interchangeability into higher level 'meta-problem' representations of the original CSP.

Values may become interchangeable or substitutable during backtrack search after some variables have been instantiated, so even a problem with no interchangeable values may exhibit interchangeability under some search strategy.

Dynamic Neighborhood Interchangeability (DynNI)5 [Beckwith and Choueiry, 2001] Two values a and b for variable X are DynNI with respect to a set A of variable assignments iff they are NI in the subproblem induced by A ∪ {X} .

## Theorem 11. Ni → Dynni.

Consider values a and b for a variable v that are NI, assume a and b are not DynNI. Then, for an assignment for the subset of variables S, either a and b are not NI in the problem induced by V \ S, or one of a or b is deleted. The former case is impossible because a and b have the same set of supports in the original problem, and thus must have the same supports after the assignments. The latter case is also impossible because a and b having the same support sets, if a loses all its supports in a neighboring variable, then b also loses all supports because the support sets are the same.

Full Dynamic Interchangeability (FDynI) [Prestwich, 2004a] A value a for variable v is dynamically interchangeable for b with respect to a set A of variable assignments iff they are fully interchangeable in the subproblem induced by A.

## Theorem 12. Dynni → Fdyni.

If a and b are DynNI, then a and b are consistent with the same set of values in the assignment A. They are also NI relative to the variables in the problem induced by A that are not yet assigned and, consequently, are FI.

Functional interchangeability [Freuder, 1991] Let Sa|X be the set of solutions including value a for variable X. Two values a for X and b for Y are *functionally* interchangeable iff there exists functions f and f 0such that f(Sa|X) = Sb|Y and f(Sb|Y ) = Sa|X.

Two values a and b for a variable are *isomorphically interchangeable* [Freuder, 1991] iff there exists a 1-1 function f such that b = f(a) and for any solution S involving a, {f(v) | v ∈ S} is a solution. Also for any solution S involving b, {f
−1(v) | v ∈ S} is a solution.

In the longer version of this paper, we compare functional and isomorphic interchangeability with the definitions of symmetry introduced in [Benhamou, 1994; Cohen *et al.*, 2006].

5 Dynamic Interchangeability (DynI) property was incorrectly characterized as Dynamic Neighborhood Partial Interchangeability (DNPI) in [Beckwith and Choueiry, 2001; Choueiry and Davis, 2002; Lal and Choueiry, 2004; Lal *et al.*, 2005].