Many-to-many interchangeable sets of values in CSPs

Abstract

Onto-substitutability has been shown to be intrinsic to how a domain value is considered redundant. A value is onto-substitutable if any solution involving that value remains a solution when that value is replaced by some other value. We redefine onto-substitutability to accommodate binary relationships and study its implication. Joint interchangeability, an extension of onto-substitutability to its interchangeabil-ity counterpart, emerges as one of the results. We propose a new way of removing interchangeable values by constructing a new value as an intermediate step, as well as introduce virtual interchangeability, a local reasoning that leads to joint interchangeability and allows values to be merged together. Copyright 2013 ACM.