Language, Definition and Optimal Computation of CSP Approximations

May 2003

Proceedings of the Sixteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2003)

Volume

Proceedings of the Sixteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2003)

All Papers

In this paper, we introduce a formal framework to describe CSP approximations (usually called consistencies), showing the importance of the language (or datastructure) 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.