Brauer, Jorg and King, Andy and Kriener, Jael (2011) Existential Quantification as Incremental SAT: 23rd International Conference, CAV 2011, Snowbird, UT, USA, July 14-20, 2011. Proceedings. In: Gopalakrishnan, Ganesh and Qadeer, Shaz, eds. Computer Aided Verification. Lecture Notes in Computer Science, 6806 . Springer, pp. 191-207. ISBN 978-3-642-22109-5. (doi:https://doi.org/10.1007/978-3-642-22110-1_17) (Full text available)
Download (369kB)
Preview
|
|
|
Official URL http://dx.doi.org/10.1007/978-3-642-22110-1_17 |
Abstract
This paper presents an elegant algorithm for existential quantifier elimination using incremental SAT solving. This approach contrasts with existing techniques in that it is based solely on manipulating the SAT instance rather than requiring any reengineering of the SAT solver or needing an auxiliary data-structure such as a BDD. The algorithm combines model enumeration with the generation of shortest prime implicants so as to converge onto a quantifier-free formula presented in CNF. We apply the technique to a number of hardware circuits and transfer functions to demonstrate the effectiveness of the method.
Item Type: | Book section |
---|---|
Subjects: | A General Works |
Divisions: | Faculties > Sciences > School of Computing > Programming Languages and Systems Group |
Depositing User: | Andy King |
Date Deposited: | 12 Dec 2013 21:13 UTC |
Last Modified: | 07 Jul 2015 10:07 UTC |
Resource URI: | https://kar.kent.ac.uk/id/eprint/37589 (The current URI for this page, for reference purposes) |
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):