Existential Quantification as Incremental SAT: 23rd International Conference, CAV 2011, Snowbird, UT, USA, July 14-20, 2011. Proceedings

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)

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)