Talks and Poster Presentations (with Proceedings-Entry):
M. R. Fellows, A. Pfandler, F. A. Rosamond, St. Rümmele:
"The Parameterized Complexity of Abduction";
Talk: AAAI Conference,
- 07-26-2012; in: "Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence",
J. Hoffmann, B. Selman (ed.);
Abduction belongs to the most fundamental reasoning
methods. It is a method for reverse inference, this means
one is interested in explaining observed behavior by
finding appropriate causes. We study logic-based abduction,
where knowledge is represented by propositional
formulas. The computational complexity of this
problem is highly intractable in many interesting settings.
In this work we therefore present an extensive
parameterized complexity analysis of abduction within
various fragments of propositional logic together with
(combinations of) natural parameters.
Project Head Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung
Created from the Publication Database of the Vienna University of Technology.