Incrementally Solving Functional Constraints

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Student Abstracts

Binary functional constraints represent an important constraint class. An efficient algorithm for determining satisfiability of a static system of functional constraints in O(ed) time is known where e is the number of constraints and d is the size of the domain. However, in most constraint programming systems, constraints are incrementally added to the constraint store. Here, we describe how satisfiability of an incremental system of only functional constraints can be obtained in almost the same time complexity as the static one. In a mixed incremental CSP which contains also non-functional constraints, we propose an algorithm which does eagerelimination to achieve more consistency on the mixed system. The resulting algorithm has complexity O(ed^2 log e) which is comparable to the cost of enforcing arc consistency.