37 citations · 66 across the 10 of their papers we have counts for
11 papers
The Complexity of Monotone Hybrid Logics over Linear Frames and the Natural Numbers
Stefan Göller, Arne Meier, Martin Mundhenk +3
Hybrid logic with binders is an expressive specification language. Its satisfiability problem is undecidable in general. If frames are restricted to N or general linear orders, the…
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…
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…
Complexity of Non-Monotonic Logics
Michael Thomas, Heribert Vollmer
Over the past few decades, non-monotonic reasoning has developed to be one of the most important topics in computational logic and artificial intelligence. Different ways to introd…
Complexity Classifications for Propositional Abduction in Post's Framework
Nadia Creignou, Johannes Schmidt, Michael Thomas
In this paper we investigate the complexity of abduction, a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining the world's behavior it aim…
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…