FMCAD 2004 START ConferenceManager    


QuBE++: an Efficient QBF Solver

Enrico Giunchiglia, Massimo Narizzano, Armando Tacchella

Presented at Formal Methods in Computer-Aided Design (FMCAD 2004), Austin, Texas, November 14-17, 2004


Abstract

In this paper we describe QUBE++, an efficient solver for Quantified Boolean Formulas (QBFs). To the extent of our knowledge, QUBE++ is the first QBF reasoning engine that solves mixed CNF/DNF instances using lazy data structures both for unit clauses propagation and for pure literals detection. QUBE++ also features a specifically tailored non-chronological backtracking method and a branching heuristic that leverages the information gathered during the backtracking phase. Owing to such techniques and to a careful implementation, QUBE++ turns out to be an efficient and robust solver, whose performances exceed those of other state-of-the-art QBF engines, and are comparable with the best engines currently available on SAT instances.


  
START Conference Manager (V2.46.3)
Maintainer: sanders@cs.ubc.ca