Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

The Parameterized Complexity of Abduction

Fellows, Michael, Pfandler, Andreas, Rosamond, Frances and Rummele, Stefan (2012). The Parameterized Complexity of Abduction. In: AAAI-12 Conference on Artificial Intelligence 2012, Toronto, Ontario Canada, 22-26 July 2012.

Document type: Conference Paper

IRMA ID 82794376xPUB23
Author Fellows, Michael
Pfandler, Andreas
Rosamond, Frances
Rummele, Stefan
Title The Parameterized Complexity of Abduction
Conference Name AAAI-12 Conference on Artificial Intelligence 2012
Conference Location Toronto, Ontario Canada
Conference Dates 22-26 July 2012
Conference Publication Title Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence
Publisher Association for the Advancement of Artificial Intelligence (AAAI) Press
Publication Year 2012
ISBN 978-1-57735-568-7   (check CDU catalogue open catalogue search in new window)
Start Page 743
End Page 749
Total Pages 7
HERDC Category E1 - Conference Publication (DIISR)
Abstract 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.
Keyword Abduction
Complexity Theory
Parameterized Complexity Theory
Kernelization
Description for Link Link to conference proceedings
URL http://www.aaai.org/Press/Proceedings/aaai12.php
 
Versions
Version Filter Type
Access Statistics: 48 Abstract Views  -  Detailed Statistics
Created: Fri, 17 Jan 2014, 00:19:45 CST