37 citations · 80 across the 29 of their papers we have counts for
Showing 2011Show all
3 papers · 1 filter
cs.CC2011★ 1 cited
On the Parameterized Complexity of Default Logic and Autoepistemic Logic
Arne Meier, Johannes Schmidt, Michael Thomas +1
We investigate the application of Courcelle's Theorem and the logspace version of Elberfeld etal. in the context of the implication problem for propositional sets of formulae, the…
cs.LO2011★ 8 cited
Generalized Satisfiability for the Description Logic ALC
Arne Meier, Thomas Schneider
The standard reasoning problem, concept satisfiability, in the basic description logic ALC is PSPACE-complete, and it is EXPTIME-complete in the presence of unrestricted axioms. Se…
cs.LO2011★ 9 cited
Model Checking CTL is Almost Always Inherently Sequential
Olaf Beyersdorff, Arne Meier, Martin Mundhenk +3
The model checking problem for CTL is known to be P-complete (Clarke, Emerson, and Sistla (1986), see Schnoebelen (2002)). We consider fragments of CTL obtained by restricting the…