Existential Quantification as Incremental SAT

Brauer, Jorg and King, Andy and Kriener, Jael (2011) Existential Quantification as Incremental SAT. In: Twenty Third International Conference on Computer Aided Verification. (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided)

The full text of this publication is not available from this repository. (Contact us about this Publication)
Official URL


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: Conference or workshop item (UNSPECIFIED)
Uncontrolled keywords: determinacy analysis, Craig interpolants
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Science Technology and Medical Studies > School of Computing > Programming Languages and Systems Group
Depositing User: Andy King
Date Deposited: 21 Sep 2012 09:49
Last Modified: 16 Dec 2013 11:30
Resource URI: https://kar.kent.ac.uk/id/eprint/30743 (The current URI for this page, for reference purposes)
  • Depositors only (login required):


Downloads per month over past year