A GENERIC ARC-CONSISTENCY ALGORITHM AND ITS SPECIALIZATIONS

Consistency techniques have been studied extensively in the past as a way of tackling constraint satisfaction problems (CSP). In particular, various arc-consistency algorithms have been proposed, originating from Waltz's filtering algorithm [271 and culminating in the optimal algorithm AC-4 of Mohr and Henderson [16]. AC-4 runs in O(ed2) in the worst case, where e is the number of arcs (or constraints) and d is the size of the largest domain. Being applicable to the whole class of (binary) CSP, these algorithms do not take into account the semantics of constraints. In this paper, we,present a new generic arc-consistency algorithm AC-5. This algorithm is parametrized on two specified procedures and can be instantiated to reduce to AC-3 and AC-4. More important, AC-5 can be instantiated to produce an O(ed) algorithm for a number of important classes of constraints: functional, anti-functional. monotonic, and their generalization to (functional, anti-functional, and monotonic) piecewise constraints. We also show that AC-5 has an important application in constraint logic programming over finite domains [241. The kernel of the constraint solver for such a programming language is an arc-consistency algorithm for a set of basic constraints. We prove that AC-5, in conjunction with node consistency, provides a decision procedure for these constraints running in time O(ed).