Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
A. Pfandler, St. Rümmele, St. Szeider:
"Backdoors to Abduction";
Vortrag: Twenty-third International Conference on Artificial Intelligence (IJCAI-13),
Peking, China;
03.08.2013
- 09.08.2013; in: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence",
F. Rossi (Hrg.);
AAAI Press,
(2013),
ISBN: 978-1-57735-633-2;
S. 1046
- 1052.
Kurzfassung englisch:
Abductive reasoning (or Abduction, for short) is among the most fundamental AI reasoning methods, with a broad range of applications, including fault diagnosis, belief revision, and automated planning. Unfortunately, Abduction is of high computational complexity; even propositional Abduction is ΣP2-complete and thus harder than NP and co-NP. This complexity barrier rules out the existence of a polynomial transformation to propositional satisfiability (SAT). In this work we use structural properties of the Abduction instance to break this complexity barrier. We utilize the problem structure in terms of small backdoor sets. We present fixed-parameter tractable transformations from Abduction to SAT, which make the power of today´s SAT solvers available to Abduction.
Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen
Projektleitung Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.