The Parameterized Complexity of Abduction

Michael Fellows, Andreas Pfandler, Frances Rosamond, Stefan Rummele

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

    14 Downloads (Pure)

    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.
    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)
    Pages743-749
    Number of pages7
    Volume1
    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)

    Conference

    ConferenceAssociation for the Advancement of Artificial Intelligence Conference (AAAI 2012 26th)
    Abbreviated titleAAAI
    CountryCanada
    CityToronto
    Period22/07/1226/07/12

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

  • Cite this

    Fellows, M., Pfandler, A., Rosamond, F., & Rummele, S. (2012). The Parameterized Complexity of Abduction. In J. Hoffmann, & B. Selman (Eds.), Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (Vol. 1, pp. 743-749). Association for the Advancement of Artificial Intelligence (AAAI).