You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

The (D)QBF Preprocessor HQSpre – Underlying Theory and Its Implementation1

Issue title: SAT 2018 Competitions and Evaluations

Guest editors: Martina Seidl and Luca Pulina

Article type: Research Article

Authors: Wimmer, Ralfa | Scholl, Christophb | Becker, Berndb

Affiliations: [a] Concept Engineering GmbH and Albert-Ludwigs-Universität Freiburg, Freiburg im Breisgau, Germany. E-mail: [email protected] | [b] Albert-Ludwigs-Universität Freiburg, Freiburg im Breisgau, Germany. E-mails: [email protected], [email protected]

Note: [1] This work was partly supported by the German Research Council (DFG) as part of the project “Solving Dependency Quantified Boolean Formulas”. It extends the conference publications [77] and [79] by additional theoretical results on (D)QBF preprocessing techniques, more (and more recent) details on the implementation of HQSpre, complete proofs for all statements, and new experimental results on benchmarks from QBFEVAL’18.

Keywords: Preprocessing, DQBF, Solver technology, Henkin quantifiers

DOI: 10.3233/SAT190115

Journal: Journal on Satisfiability, Boolean Modeling and Computation, vol. 11, no. 1, pp. 3-52, 2019

Received 1 November 2018
|
Revision received 1 March 2019
|
Published: 1 September 2019
Get PDF open access

Abstract

Preprocessing turned out to be an essential step for SAT, QBF, and DQBF solvers to reduce/modify the number of variables and clauses of the formula, before the formula is passed to the actual solving algorithm. These preprocessing techniques often reduce the computation time of the solver by orders of magnitude. In this paper, we present the preprocessor HQSpre that was developed for Dependency Quantified Boolean Formulas (DQBFs) and that generalizes different preprocessing techniques for SAT and QBF problems to DQBF. We give a presentation of the underlying theory together with detailed proofs as well as implementation details contributing to the efficiency of the preprocessor. HQSpre has been used with obvious success by the winners of the DQBF track, and, even more interestingly, the QBF tracks of QBFEVAL’18.

Show more