The Parameterized Complexity of Abduction

Michael Fellows, Andreas Pfandler, Frances Rosamond, Stefan Rummele

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

    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

    Computational complexity

    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). Online: Association for the Advancement of Artificial Intelligence (AAAI).
    Fellows, Michael ; Pfandler, Andreas ; Rosamond, Frances ; Rummele, Stefan. / The Parameterized Complexity of Abduction. Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. editor / Jorg Hoffmann ; Bart Selman. Vol. 1 Online : Association for the Advancement of Artificial Intelligence (AAAI), 2012. pp. 743-749
    @inproceedings{4c4d413480d34f2fadfb0adbd8e75345,
    title = "The Parameterized Complexity of Abduction",
    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.",
    keywords = "Parameterized complexity, Propositional formulas, Propositional logic, Reasoning methods, Formal logic, Artificial intelligence",
    author = "Michael Fellows and Andreas Pfandler and Frances Rosamond and Stefan Rummele",
    year = "2012",
    language = "English",
    isbn = "978-1-57735-568-7",
    volume = "1",
    pages = "743--749",
    editor = "Jorg Hoffmann and Bart Selman",
    booktitle = "Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence",
    publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

    }

    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, Association for the Advancement of Artificial Intelligence (AAAI), Online, pp. 743-749, Association for the Advancement of Artificial Intelligence Conference (AAAI 2012 26th), Toronto, Canada, 22/07/12.

    The Parameterized Complexity of Abduction. / Fellows, Michael; Pfandler, Andreas; Rosamond, Frances; Rummele, Stefan.

    Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. ed. / Jorg Hoffmann; Bart Selman. Vol. 1 Online : Association for the Advancement of Artificial Intelligence (AAAI), 2012. p. 743-749.

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

    TY - GEN

    T1 - The Parameterized Complexity of Abduction

    AU - Fellows, Michael

    AU - Pfandler, Andreas

    AU - Rosamond, Frances

    AU - Rummele, Stefan

    PY - 2012

    Y1 - 2012

    N2 - 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.

    AB - 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.

    KW - Parameterized complexity

    KW - Propositional formulas

    KW - Propositional logic

    KW - Reasoning methods

    KW - Formal logic

    KW - Artificial intelligence

    UR - http://www.aaai.org/Press/Proceedings/aaai12.php

    M3 - Conference Paper published in Proceedings

    SN - 978-1-57735-568-7

    VL - 1

    SP - 743

    EP - 749

    BT - Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence

    A2 - Hoffmann, Jorg

    A2 - Selman, Bart

    PB - Association for the Advancement of Artificial Intelligence (AAAI)

    CY - Online

    ER -

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