6 citations · 12 across the 10 of their papers we have counts for
5 papers · 1 filter
Model Counting for Dependency Quantified Boolean Formulas
Long-Hin Fung, Che Cheng, Jie-Hong Roland Jiang +2
Dependency Quantified Boolean Formulas (DQBF) generalize QBF by explicitly specifying which universal variables each existential variable depends on, instead of relying on a linear…
Structure-Aware Lower Bounds and Broadening the Horizon of Tractability for QBF
Johannes K. Fichte, Robert Ganian, Markus Hecher +2
The QSAT problem, which asks to evaluate a quantified Boolean formula (QBF), is of fundamental interest in approximation, counting, decision, and probabilistic complexity and is al…
Towards Uniform Certification in QBF
Leroy Chew, Friedrich Slivovsky
We pioneer a new technique that allows us to prove a multitude of previously open simulations in QBF proof complexity. In particular, we show that extended QBF Frege p-simulates cl…
Certified DQBF Solving by Definition Extraction
Franz-Xaver Reichl, Friedrich Slivovsky, Stefan Szeider
We propose a new decision procedure for dependency quantified Boolean formulas (DQBF) that uses interpolation-based definition extraction to compute Skolem functions in a counter-e…
On Compiling Structured CNFs to OBDDs
Simone Bova, Friedrich Slivovsky
We present new results on the size of OBDD representations of structurally characterized classes of CNF formulas. First, we identify a natural sufficient condition, which we call t…