Abandoning Prenex Clausal Normal Form in QBF Solving

360 views · Published 17 August 2016 · 1:05:15 · Indexed 23 October 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

In the last decades, numerous successful QSAT solvers have been developed. However, most of these solvers process formulas only in prenex conjunctive normal form (PCNF).  As for many practical applications encodings into QBFs usually do not result in PCNF formulas, a further transformation step is  necessary. This transformation often introduces new variables and disrupts the structure of the formula.  In this talk, we discuss the disadvantages of prenex conjunctive normal form and describe an alternative way to process QBFs without the drawbacks of the normal form transformation. We briefly describe the  solver qpro, which is able to handle formulas in negation normal form. To this end, we extend algorithms for QBFs to the non-normal form case and generalize well-known pruning concepts. For a concise description of the extended algorithms, we follow a sequent-style characterization approach.

More from this channel