Language, Definition and Optimal Computation of CSP Approximations

Arnaud Lallouet, Thi Bich Hanh Dao, and Abdel Ali Ed-Dbali

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.