10 citations · 30 across the 15 of their papers we have counts for
4 papers · 1 filter
Expressing Linear Orders Requires Exponential-Size DNNFs
Ronald de Haan
We show that any DNNF circuit that expresses the set of linear orders over a set of candidates must be of size . Moreover, we show that there exist DNNF circuits of s…
On the Computational Complexity of Model Checking for Dynamic Epistemic Logic with S5 Models
Ronald de Haan, Iris van de Pol
Dynamic epistemic logic (DEL) is a logical framework for representing and reasoning about knowledge change for multiple agents. An important computational task in this framework is…
The Parameterized Complexity of Reasoning Problems Beyond NP
Ronald de Haan, Stefan Szeider
Today's propositional satisfiability (SAT) solvers are extremely powerful and can be used as an efficient back-end for solving NP-complete problems. However, many fundamental probl…
Local Backbones
Ronald de Haan, Iyad Kanj, Stefan Szeider
A backbone of a propositional CNF formula is a variable whose truth value is the same in every truth assignment that satisfies the formula. The notion of backbones for CNF formulas…