QBF Solving by Counterexample-guided Expansion
This addresses a bottleneck in QBF solving for applications in formal verification and automated reasoning, though it appears incremental as it builds on existing CEGIS methods.
The paper tackles the poor scaling of recursive counterexample-guided expansion approaches for solving Quantified Boolean Formulas (QBF) with many quantifier alternations, by introducing a generalization of Counterexample-Guided Inductive Synthesis (CEGIS) that removes the need for recursion and yields a simple, efficient algorithm.
We introduce a novel generalization of Counterexample-Guided Inductive Synthesis (CEGIS) and instantiate it to yield a novel, competitive algorithm for solving Quantified Boolean Formulas (QBF). Current QBF solvers based on counterexample-guided expansion use a recursive approach which scales poorly with the number of quantifier alternations. Our generalization of CEGIS removes the need for this recursive approach, and we instantiate it to yield a simple and efficient algorithm for QBF solving. Lastly, this research is supported by a competitive, though straightforward, implementation of the algorithm, making it possible to study the practical impact of our algorithm design decisions, along with various optimizations.