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.
Brauer, King, and Kriener REF designed an algorithm that combines model enumeration with prime implicant generation.
Existential Quantification as Incremental SAT
In Twenty-third International Conference on Computer Aided Verification, G. Gopalakrishnan and
Computer Science