First, consider NI → NTI. Given values a and b that are NI for a variable, for every consistent tuple t with a there is a tuple t 0that only differs from t with a replaced with b. Hence t and t 0 are consistent with the same value combinations.

Figure 12 gives an example where the converse does not hold. For (NTI → PI)
and (NTI → NPI), see [Neagu and Faltings, 2005]. Figure 4 gives an example where PI 6→ NTI, and Figure 11 gives an example where NPI 6→ NTI.

In [2005], Wilson described a new approach to computation in a semiringbased system based on semiring-labeled decision diagrams (SLDDs). He defines forward neighborhood interchangeability (ForwNI) and uses it for merging nodes in SLDDs, hence compacting the search space. During search, ForwNI takes into account constraints that apply to instantiated and uninstantiated variables.

Forward Neighborhood Interchangeability (ForwNI) [Wilson, 2005] Given a subset of variables U ⊂ V , two assignments u and u 0to a set of variables U are said to be ForwNI if for all constraints c ∈ C such that *scope*(c) ∩ (V \ U) 6= ∅
and *scope*(c) ∩ U 6= ∅, ΠV \U {t ∈ c | ΠU (t) = u} = ΠV \U {t ∈ c | ΠU (t) = u 0}.

Theorem 15. NTI → ForwNI. If a and b for variable X are NTI with respect to set of variables S, then for every assignment t to S ∪ {X} where X = a there is another consistent tuple t 0 where X = b such that t and t 0 are consistent with the same value combinations for variables outside of S. Hence, the set of tuples consistent with t is the same for t 0 when projected on V \S. Therefore, the assignments ΠS(t) and ΠS(t 0) are ForwNI.

Tuple substitutability is a global form of ForwNI:
Tuple Substitutability (TupSub) [Jeavons *et al.*, 1994] Two assignments A
and B to a set of variables R are TupSub iff ΠV \R(σB(Sol)) ⊆ ΠV \R(σA(Sol)),
where Sol is the set of all solutions to the problem.

## Theorem 16. Forwni → Tupsub.

If two assignments u and u 0 are ForwNI, then for every solution in which u participates, u can be substituted with u 0 because they have the same supports in every constraint that links the scope of u to the rest of the problem. Therefore, the assignments u and u 0 are interchangeable and consequently substitutable.

## Theorem 17. Dynni → Forwni.

If a and b for variable X is DynNI wrt a set A of assignments, then any two assignments u and u 0in A ∪ {X}, such that ΠX(u) = a and ΠX(u 0) = b, have the same set of support tuples because a and b are NI in V \A. Therefore, u and u 0 are ForwNI.

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

Theorem 18. FDynI → FDynSub, follows directly from the definition.