Language, Definition and Optimal Computation of CSP Approximations

摘要

In this paper, we introduce a formal framework to describe CSP approximations (usually called consistencies), showing the importance of the language (or data-structure) used to perform this consistency. We introduce the notion of R-consistency which takes into account the representation of the data and which generalizes many known consistencies. We then automatically derive from a CSP and its approximation scheme a rule system describing the constraint propagation and we propose an optimal algorithm in the spirit of AC4 to achieve it.