The Parameterized Complexity of Abduction

Michael Fellows, Andreas Pfandler, Frances Rosamond, Stefan Rummele

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review

    12 Citations (Scopus)
    14 Downloads (Pure)


    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.
    Original languageEnglish
    Title of host publicationProceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence
    EditorsJorg Hoffmann, Bart Selman
    Place of PublicationOnline
    PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
    Number of pages7
    ISBN (Print)978-1-57735-568-7
    Publication statusPublished - 2012
    EventAssociation for the Advancement of Artificial Intelligence Conference (AAAI 2012 26th) - Toronto, Ontario, Canada, Toronto, Canada
    Duration: 22 Jul 201226 Jul 2012
    Conference number: 2012 (26th)


    ConferenceAssociation for the Advancement of Artificial Intelligence Conference (AAAI 2012 26th)
    Abbreviated titleAAAI


    Dive into the research topics of 'The Parameterized Complexity of Abduction'. Together they form a unique fingerprint.

    Cite this