37 citations · 66 across the 10 of their papers we have counts for
7 papers · 1 filter
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…
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…
Complexity of Propositional Abduction for Restricted Sets of Boolean Functions
Nadia Creignou, Johannes Schmidt, Michael Thomas
Abduction is a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining how the world behaves it aims at finding an explanation for some observe…
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…