37 citations · 80 across the 29 of their papers we have counts for
Showing 2008Show all
2 papers · 1 filter
cs.CC2008★ 37 cited
The Complexity of Propositional Implication
Olaf Beyersdorff, Arne Meier, Michael Thomas +1
The question whether a set of formulae G implies a formula f is fundamental. The present paper studies the complexity of the above implication problem for propositional formulae th…
cs.CC2008
The Complexity of Reasoning for Fragments of Default Logic
Olaf Beyersdorff, Arne Meier, Michael Thomas +1
Default logic was introduced by Reiter in 1980. In 1992, Gottlob classified the complexity of the extension existence problem for propositional default logic as $\SigmaPtwo$-comple…