On the Computation of Local Interchangeability in Discrete Constraint Satisfaction Problems

In [4], Freuderdefines several types of interchangeability to capture the equivalenceamong the valuesof a variable in a discrete constraint satisfaction problem(CSP), and provides a procedure for computing onetype of local interchangeability. In this paper, we first extendthis procedurefor computing a weak form of local interchangeability. Second, weshowthat the modifiedprocedurecanbe used to generate a conjunctive decompositionof the CSPby localizing, in the CSP, independentsubproblems. Third, for the case of constraints of mutualexclusion, weshowthat locally interchangeablevaluescan be computed in a straightforward manner, and that the only possible type of local interchangeabilityis the onethat induceslocally independentsubproblems. Finally, wegive hints on how to exploit these results in practice, establish a lattice that relates some types of interchangeability, andidentify directions for future research.

Authors

• Berthe Y. Choueiry Kai-Chen Huang

Keywords

No keywords are indexed for this paper.