1 citations · 4 across the 9 of their papers we have counts for
10 papers
Complexity of Reasoning with Cardinality Minimality Conditions
Nadia Creignou, Frédéric Olive, Johannes Schmidt
Many AI-related reasoning problems are based on the problem of satisfiability of propositional formulas with some cardinality-minimality condition. While the complexity of the sati…
Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework
Yasir Mahmood, Arne Meier, Johannes Schmidt
Logic-based argumentation is a well-established formalism modelling nonmonotonic reasoning. It has been playing a major role in AI for decades, now. Informally, a set of formulas i…
Parameterised Complexity of Abduction in Schaefer's Framework
Yasir Mahmood, Arne Meier, Johannes Schmidt
Abductive reasoning is a non-monotonic formalism stemming from the work of Peirce. It describes the process of deriving the most plausible explanations of known facts. Considering…
The Weight in Enumeration
Johannes Schmidt
In our setting enumeration amounts to generate all solutions of a problem instance without duplicates. We address the problem of enumerating the models of B-formulae. A B-formula i…
Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
Peter Jonsson, Victor Lagerkvist, Johannes Schmidt +1
Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the…
Paradigms for Parameterized Enumeration
Nadia Creignou, Arne Meier, Julian-Steffen Müller +2
The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of para…
Complexity Classifications for logic-based Argumentation
Nadia Creignou, Uwe Egly, Johannes Schmidt
We consider logic-based argumentation in which an argument is a pair (Fi,al), where the support Fi is a minimal consistent set of formulae taken from a given knowledge base (usuall…
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 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…