

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

semantic symmetry. Hence, the terms 'semantic' and 'global' are equivalent. Because the detection of global forms of interchangeability is likely to be intractable, Freuder introduced *local* variants, which account only for the constraints defined on a variable, that is, the neighborhood of the variable. In [1994], Benhamou calls such relations *syntactic* symmetries. Section 2.1 discusses local interchangeability. Further, interchangeability is an equivalence relation on the domain of the variable: interchangeable values are equivalent. Such equivalences may be rare in practice. To remedy this situation, Freuder proposed various extensions to the basic concept, which are discussed in Sections 2.2 and 2.3.

In summary, one may think of interchangeability as a core concept characterized as a relation between two values either at the solution level (i.e., global or semantic) or in the neighborhood of the variable (i.e., local or syntactic). Also, the concepts may require that interchangeable values be equivalent (i.e., strong),
or not 'perfectly' so (i.e., weak or approximate).

When comparing two forms of interchangeability X and Y *, we say that* X →
Y iff any two values a and b that are related by X are also related by Y *but the* converse does not necessarily hold2, regardless of whether Y is derived from X
by relaxing the conditions of X (i.e., Y is weaker than X) or by 'moving' from the local level to the global level (i.e., syntactic to semantic). Note that when X → Y , Y leads to greater problem reduction than X.

## 2.1 Local Forms Of Interchangeability

In general, the identification of a local interchangeability is tractable because it focuses on the neighborhood of the variable. Also, a given local form interchangeability usually implies the corresponding global one.

Neighborhood interchangeability (NI) [Freuder, 1991] A value a for variable v is neighborhood interchangeable with value b iff for every constraint on v, the values compatible with v = a are exactly those compatible with v = b. Values a and b are NI in Figure 2 but not in Figures 1 or 3.

Neighborhood interchangeable values for a given variable can be detected by comparing the values in the variable's domain for consistency to all variablevalue pairs in the variable's neighborhood and drawing a discrimination tree 2a and b are two values or two partial assignments over the same variables.