Consistency techniques have been studied extensively in the past as a way o f t a c kling constraint satisfaction problems (CSP). In particular, various arc-consistency algorithms have been proposed, originating from Waltz's ltering algorithm 27] and culminating in the optimal algorithm AC-4 of Mohr and Henderson 16]. AC-4 runs in O(ed 2 ) i n t h e w orst 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 i n to account t h e semantics of constraints. In this paper, we present a new generic arc-consistency algorithm AC-5. This algorithm is parametrized on two speci ed 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 t h a t A C-5 has an important application in constraint logic programming over nite domains 24]. The kernel of the constraint s o l v er for such a programming language is an arc-consistency algorithm for a set of basic constraints. We p r o ve that AC-5, in conjunction with node consistency, p r o vides a decision procedure for these constraints running in time O(ed). 1 This paper is an extended version of 3].
AC-5, a new arc-consistency algorithm, is presented by REF .
A generic arc-consistency algorithm and its specializations
Artificial Intelligence
Mathematics Computer Science