Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators

Abdallah Saffidine, Andreas Herzig

It is well-known that every quantified boolean formula (QBF) can be transformed into a prenex QBF whose only boolean operators are negation, conjunction, and disjunction. It is als…