Abstract | ||
---|---|---|
SMT-based applications increasingly rely on SMT solvers being able to deal with quantified formulas. Current work shows that for formulas with quantifiers over uninterpreted sorts counter-models can be obtained by integrating a finite model finding capability into the architecture of a modern SMT solver. We examine various strategies for on-demand quantifier instantiation in this setting. Here, completeness can be achieved by considering all ground instances over the finite domain of each quantifier. However, exhaustive instantiation quickly becomes unfeasible with larger domain sizes. We propose instantiation strategies to identify and consider only a selection of ground instances that suffices to determine the satisfiability of the input formula. We also examine heuristic quantifier instantiation techniques such as E-matching for the purpose of accelerating the search. We give experimental evidence that our approach is practical for use in industrial applications and is competitive with other approaches. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/978-3-642-38574-2_26 | CADE |
Keywords | Field | DocType |
finite domain,on-demand quantifier instantiation,quantifier instantiation technique,heuristic quantifier instantiation technique,finite model finding,finite model,exhaustive instantiation,modern smt solver,instantiation strategy,ground instance,larger domain size,smt-based application | Quantifier elimination,Discrete mathematics,Heuristic,Programming language,Computer science,Satisfiability,Algorithm,Model finding,Theoretical computer science,Completeness (statistics),Satisfiability modulo theories | Conference |
Citations | PageRank | References |
14 | 0.62 | 14 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrew Reynolds | 1 | 212 | 14.79 |
Cesare Tinelli | 2 | 1409 | 79.86 |
Amit Goel | 3 | 279 | 21.29 |
Sava Krstić | 4 | 144 | 9.41 |
Morgan Deters | 5 | 283 | 17.25 |
Clark Barrett | 6 | 1268 | 108.65 |