AuthorsS. Bardin and A. Gotlieb
EditorsN. Beldiceanu, N. Jussien and É. Pinson
Titlefdcc: a Combined Approach for Solving Constraints Over Finite Domains and Arrays
AfilliationSoftware Engineering, Software Engineering, Software Engineering
Project(s)The Certus Centre (SFI)
Publication TypeProceedings, refereed
Year of Publication2012
Conference NameProceedings of CPAIOR 2012 (Constraint Programming-Artificial Intelligence-Operations Research), Nantes, France
PublisherSpringer Berlin Heidelberg
Place PublishedBerlin Heidelberg

Arrays are ubiquitous in the context of software verification. However, effective reasoning over arrays is still rare in CP, as local reasoning is dramatically ill-conditioned for constraints over arrays. In this paper, we propose an approach combining both global symbolic reasoning and local filtering in order to solve constraint systems involving arrays (with accesses, updates and size constraints) and finite-domain constraints over their elements and indexes. Our approach, named FDCC, is based on a combination of a congruence closure algorithm for the standard theory of arrays and a CP solver over finite domains. The tricky part of the work lies in the bi-directional communication mechanism between both solvers. We identify the significant information to share, and design ways to master the communication overhead. Experiments on random instances show that FDCC solves more formulas than any portfolio combination of the two solvers taken in isolation, while overhead is kept reasonable.

Citation KeySimula.simula.1220