Arrays are ubiquitous in the context of software verication. However, eective 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 com- bining both global symbolic reasoning and local consistency ltering in order to solve constraint systems involving arrays (with accesses, updates and size constraints) and nite-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 nite domains. The tricky part of the work lies in the bi- directional communication mechanism between both solvers. We identify the signicant information to share, and design ways to master the communication overhead. Exper- iments 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.
Third, one could encode all finite-domain constraints into boolean constraints and use a SMT solver equipped with a decision procedure for the standard theory of arrays. Doing so, we give away the possibility of taking advantage of the high-level structure of the initial formula. Recent works on finite but hard-to-reason-about constraints, such as floating-point arithmetic @cite_27 , modular arithmetic @cite_16 or bitvectors @cite_25 , suggests that it can be much more efficient in some cases to keep the high-level view of the formula.
@cite_27 @cite_16 @cite_25
1515930456 1598706103 2004414305 1990426442
The problem of deciding the satisfiability of a quantifier-free formula with respect to a background theory, also known as Satisfiability Modulo Theories (SMT), is gaining increasing relevance in verification: representation capabilities beyond propositional logic allow for a natural modeling of real-world problems (e.g., pipeline and RTL circuits verification, proof obligations in software systems). In this paper, we focus on the case where the background theory is the combination T1∪T2 of two simpler theories. Many SMT procedures combine a boolean model enumeration with a decision procedure for T1∪T2, where conjunctions of literals can be decided by an integration schema such as Nelson-Oppen, via a structured exchange of interface formulae (e.g., equalities in the case of convex theories, disjunctions of equalities otherwise). We propose a new approach for SMT(T1∪T2), called Delayed Theory Combination, which does not require a decision procedure for T1∪T2, but only individual decision procedures for T1 and T2, which are directly integrated into the boolean model enumerator. This approach is much simpler and natural, allows each of the solvers to be implemented and optimized without taking into account the others, and it nicely encompasses the case of non-convex theories. We show the effectiveness of the approach by a thorough experimental comparison. The theory BV of bit-vectors, i.e. fixed-size arrays of bits equipped with standard low-level machine instructions, is becoming very popular in formal verification. Standard solvers for this theory are based on a bit-level encoding into propositional logic and SAT-based resolution techniques. In this paper, we investigate an alternative approach based on a word-level encoding into bounded arithmetic and Constraint Logic Programming (CLP) resolution techniques. We define an original CLP framework (domains and propagators) dedicated to bit-vector constraints. This framework is implemented in a prototype and thorough experimental studies have been conducted. The new approach is shown to perform much better than standard CLP-based approaches, and to considerably reduce the gap with the best SAT-based BV solvers. We propose a new translation from normal logic programs with constraints under the answer set semantics to propositional logic. Given a normal logic program, we show that by adding, for each loop in the program, a corresponding loop formula to the program's completion, we obtain a one-to-one correspondence between the answer sets of the program and the models of the resulting propositional theory. In the worst case, there may be an exponential number of loops in a logic program. To address this problem, we propose an approach that adds loop formulas a few at a time, selectively. Based on these results, we implement a system called ASSAT(X), depending on the SAT solver X used, for computing one answer set of a normal logic program with constraints. We test the system on a variety of benchmarks including the graph coloring, the blocks world planning, and Hamiltonian Circuit domains. Our experimental results show that in these domains, for the task of generating one answer set of a normal logic program, our system has a clear edge over the state-of-art answer set programming systems Smodels and DLV. Abstract We present in this paper a unified processing for real, integer, and Boolean constraints based on a general narrowing algorithm which applies to any n-ary relation on R. The basic idea is to define, for every such relation ρ, a narrowing function ρ based on the approximation of ρ by a Cartesian product of intervals whose bounds are floating-point numbers. We then focus on nonconvex relations and establish several properties. The more important of these properties is applied to justify the computation of usual relations defined in terms of intersections of simpler relations. We extend the scope of the narrowing algorithm used in the language BNR-Prolog to integer and disequality constraints, to Boolean constraints, and to relations mixing numerical and Boolean values. As a result, we propose a new Constraint Logic Programming language called CLP(BNR), where BNR stands for Booleans, Naturals, and Reals. In this language, constraints are expressed in a unique structure, allowing the mixing of real numbers, integers, and Booleans. We end with the presentation of several examples showing the advantages of such an approach from the point of view of the expressiveness, and give some preliminary computational results from a prototype.