37 citations · 66 across the 10 of their papers we have counts for
4 papers · 1 filter
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…
The Complexity of Reasoning for Fragments of Autoepistemic Logic
Nadia Creignou, Arne Meier, Michael Thomas +1
Autoepistemic logic extends propositional logic by the modal operator L. A formula that is preceded by an L is said to be "believed". The logic was introduced by Moore 1985 for mod…
The Complexity of Satisfiability for Fragments of Hybrid Logic -- Part I
Arne Meier, Martin Mundhenk, Thomas Schneider +3
The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments. In this pa…
Extensional Uniformity for Boolean Circuits
Pierre McKenzie, Michael Thomas, Heribert Vollmer
Imposing an extensional uniformity condition on a non-uniform circuit complexity class C means simply intersecting C with a uniform class L. By contrast, the usual intensional unif…