Quantifier Shifting for Quantified Boolean Formulas Revisited
Sprache des Vortragstitels:
Englisch
Original Tagungtitel:
12th International Joint Conference, IJCAR 2024
Sprache des Tagungstitel:
Englisch
Original Kurzfassung:
Modern solvers for quantified Boolean formulas (QBFs) process formulas in prenex form, which divides each QBF into two parts: the quantifier prefix and the propositional matrix. While this representation does not cover the full language of QBF, every non-prenex formula can be transformed to an equivalent formula in prenex form. This transformation offers several degrees of freedom and blurs structural information that might be useful for the solvers. In a case study conducted 20 years back, it has been shown that the applied transformation strategy heavily impacts solving time. We revisit this work and investigate how sensitive recent QBF solvers perform w.r.t. various prenexing strategies.
Forschungs-