[Back]

U. Egly, F. Lonsing, M. Widl:
"Long-Distance Resolution: Proof Generation and Strategy Extraction in Search-Based QBF Solving";
Talk: International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR), Stellenbosch, South Africa; 2013-12-15 - 2013-12-19; in: "Logic for Programming, Artificial Intelligence, and Reasoning", Springer, 8312 (2013), ISBN: 978-3-642-45220-8; 291 - 308.

Strategies (and certificates) for quantified Boolean formulas (QBFs) are of high practical relevance as they facilitate the verification of results returned by QBF
solvers and the generation of solutions to problems formulated as QBFs. State of the art approaches to obtain strategies require traversing a Q-resolution proof of a QBF, which for many real-life instances is too large to handle. In this work, we consider the long-distance Q-resolution (LDQ) calculus, which allows particular tautological resolvents. We show that for a family of QBFs using LDQ allows for
exponentially shorter proofs compared to Q-resolution. We further show that an approach to strategy extraction originally presented for Q-resolution proofs can also be applied to LDQ-resolution proofs. As a practical application, we consider search-based QBF solvers which are able to learn tautological clauses based on resolution and the conflict-driven clause learning method. We prove that the resolution proofs produced by these solvers correspond to proofs in the LDQ calculus and can therefore be used as input for strategy extraction algorithms.
Experimental results illustrate the potential of the LDQ calculus in
search-based QBF solving.

QBF, QBF solving, strategy extraction

http://dx.doi.org/10.1007/978-3-642-45221-5

Project Head Uwe Egly:
FAME: Formalisierung und Handhabung von Evolution in modellbasierter Softwareentwicklung

Project Head Uwe Egly:
Quantified Boolean Formulas