Loading [MathJax]/extensions/tex2jax.js

Parameterised Complexity of Abduction in Schaefer’s Framework

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Autorschaft

Externe Organisationen

  • Universität Jönköping

Details

OriginalspracheEnglisch
Titel des SammelwerksLogical Foundations of Computer Science (LFCS 2020)
UntertitelInternational Symposium, LFCS 2020, Proceedings
Herausgeber/-innenSergei Artemov, Anil Nerode
ErscheinungsortCham
Seiten195-213
Seitenumfang19
ISBN (elektronisch)978-3-030-36755-8
PublikationsstatusVeröffentlicht - 2020
VeranstaltungInternational Symposium on Logical Foundations of Computer Science, LFCS 2020 - Deerfield Beach, USA / Vereinigte Staaten
Dauer: 4 Jan. 20207 Jan. 2020

Publikationsreihe

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band11972 LNCS
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349

Abstract

Abductive reasoning is a non-monotonic formalism stemming from the work of Peirce. It describes the process of deriving the most plausible explanations of known facts. Considering the positive version asking for sets of variables as explanations, we study, besides asking for existence of the set of explanations, two explanation size limited variants of this reasoning problem (less than or equal to, and equal to). In this paper, we present a thorough two-dimensional classification of these problems. The first dimension is regarding the parameterised complexity under a wealth of different parameterisations. The second dimension spans through all possible Boolean fragments of these problems in Schaefer’s constraint satisfaction framework with co-clones (STOC 1978). Thereby, we almost complete the parameterised picture started by Fellows et al. (AAAI 2012), partially building on results of Nordh and Zanuttini (Artif. Intell. 2008). In this process, we outline a fine-grained analysis of the inherent parameterised intractability of these problems and pinpoint their FPT parts. As the standard algebraic approach is not applicable to our problems, we develop an alternative method that makes the algebraic tools partially available again.

ASJC Scopus Sachgebiete

Zitieren

Parameterised Complexity of Abduction in Schaefer’s Framework. / Mahmood, Yasir; Meier, Arne; Schmidt, Johannes.
Logical Foundations of Computer Science (LFCS 2020): International Symposium, LFCS 2020, Proceedings. Hrsg. / Sergei Artemov; Anil Nerode. Cham, 2020. S. 195-213 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 11972 LNCS).

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Mahmood, Y, Meier, A & Schmidt, J 2020, Parameterised Complexity of Abduction in Schaefer’s Framework. in S Artemov & A Nerode (Hrsg.), Logical Foundations of Computer Science (LFCS 2020): International Symposium, LFCS 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bd. 11972 LNCS, Cham, S. 195-213, International Symposium on Logical Foundations of Computer Science, LFCS 2020, Deerfield Beach, USA / Vereinigte Staaten, 4 Jan. 2020. https://doi.org/10.48550/arXiv.1906.00703, https://doi.org/10.1007/978-3-030-36755-8_13
Mahmood, Y., Meier, A., & Schmidt, J. (2020). Parameterised Complexity of Abduction in Schaefer’s Framework. In S. Artemov, & A. Nerode (Hrsg.), Logical Foundations of Computer Science (LFCS 2020): International Symposium, LFCS 2020, Proceedings (S. 195-213). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 11972 LNCS).. https://doi.org/10.48550/arXiv.1906.00703, https://doi.org/10.1007/978-3-030-36755-8_13
Mahmood Y, Meier A, Schmidt J. Parameterised Complexity of Abduction in Schaefer’s Framework. in Artemov S, Nerode A, Hrsg., Logical Foundations of Computer Science (LFCS 2020): International Symposium, LFCS 2020, Proceedings. Cham. 2020. S. 195-213. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2019 Dez 20. doi: 10.48550/arXiv.1906.00703, 10.1007/978-3-030-36755-8_13
Mahmood, Yasir ; Meier, Arne ; Schmidt, Johannes. / Parameterised Complexity of Abduction in Schaefer’s Framework. Logical Foundations of Computer Science (LFCS 2020): International Symposium, LFCS 2020, Proceedings. Hrsg. / Sergei Artemov ; Anil Nerode. Cham, 2020. S. 195-213 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Download
@inproceedings{02306f2894844108ac8ce68a2ebfae53,
title = "Parameterised Complexity of Abduction in Schaefer{\textquoteright}s Framework",
abstract = "Abductive reasoning is a non-monotonic formalism stemming from the work of Peirce. It describes the process of deriving the most plausible explanations of known facts. Considering the positive version asking for sets of variables as explanations, we study, besides asking for existence of the set of explanations, two explanation size limited variants of this reasoning problem (less than or equal to, and equal to). In this paper, we present a thorough two-dimensional classification of these problems. The first dimension is regarding the parameterised complexity under a wealth of different parameterisations. The second dimension spans through all possible Boolean fragments of these problems in Schaefer{\textquoteright}s constraint satisfaction framework with co-clones (STOC 1978). Thereby, we almost complete the parameterised picture started by Fellows et al. (AAAI 2012), partially building on results of Nordh and Zanuttini (Artif. Intell. 2008). In this process, we outline a fine-grained analysis of the inherent parameterised intractability of these problems and pinpoint their FPT parts. As the standard algebraic approach is not applicable to our problems, we develop an alternative method that makes the algebraic tools partially available again.",
keywords = "Abduction, Co-clones, Parameterised complexity, Schaefer{\textquoteright}s framework",
author = "Yasir Mahmood and Arne Meier and Johannes Schmidt",
note = "Funding information: Funded by German Research Foundation (DFG), project ME 4279/1-2.; International Symposium on Logical Foundations of Computer Science, LFCS 2020 ; Conference date: 04-01-2020 Through 07-01-2020",
year = "2020",
doi = "10.48550/arXiv.1906.00703",
language = "English",
isbn = "9783030367541",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "195--213",
editor = "Sergei Artemov and Anil Nerode",
booktitle = "Logical Foundations of Computer Science (LFCS 2020)",

}

Download

TY - GEN

T1 - Parameterised Complexity of Abduction in Schaefer’s Framework

AU - Mahmood, Yasir

AU - Meier, Arne

AU - Schmidt, Johannes

N1 - Funding information: Funded by German Research Foundation (DFG), project ME 4279/1-2.

PY - 2020

Y1 - 2020

N2 - Abductive reasoning is a non-monotonic formalism stemming from the work of Peirce. It describes the process of deriving the most plausible explanations of known facts. Considering the positive version asking for sets of variables as explanations, we study, besides asking for existence of the set of explanations, two explanation size limited variants of this reasoning problem (less than or equal to, and equal to). In this paper, we present a thorough two-dimensional classification of these problems. The first dimension is regarding the parameterised complexity under a wealth of different parameterisations. The second dimension spans through all possible Boolean fragments of these problems in Schaefer’s constraint satisfaction framework with co-clones (STOC 1978). Thereby, we almost complete the parameterised picture started by Fellows et al. (AAAI 2012), partially building on results of Nordh and Zanuttini (Artif. Intell. 2008). In this process, we outline a fine-grained analysis of the inherent parameterised intractability of these problems and pinpoint their FPT parts. As the standard algebraic approach is not applicable to our problems, we develop an alternative method that makes the algebraic tools partially available again.

AB - Abductive reasoning is a non-monotonic formalism stemming from the work of Peirce. It describes the process of deriving the most plausible explanations of known facts. Considering the positive version asking for sets of variables as explanations, we study, besides asking for existence of the set of explanations, two explanation size limited variants of this reasoning problem (less than or equal to, and equal to). In this paper, we present a thorough two-dimensional classification of these problems. The first dimension is regarding the parameterised complexity under a wealth of different parameterisations. The second dimension spans through all possible Boolean fragments of these problems in Schaefer’s constraint satisfaction framework with co-clones (STOC 1978). Thereby, we almost complete the parameterised picture started by Fellows et al. (AAAI 2012), partially building on results of Nordh and Zanuttini (Artif. Intell. 2008). In this process, we outline a fine-grained analysis of the inherent parameterised intractability of these problems and pinpoint their FPT parts. As the standard algebraic approach is not applicable to our problems, we develop an alternative method that makes the algebraic tools partially available again.

KW - Abduction

KW - Co-clones

KW - Parameterised complexity

KW - Schaefer’s framework

UR - http://www.scopus.com/inward/record.url?scp=85077493558&partnerID=8YFLogxK

U2 - 10.48550/arXiv.1906.00703

DO - 10.48550/arXiv.1906.00703

M3 - Conference contribution

AN - SCOPUS:85077493558

SN - 9783030367541

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 195

EP - 213

BT - Logical Foundations of Computer Science (LFCS 2020)

A2 - Artemov, Sergei

A2 - Nerode, Anil

CY - Cham

T2 - International Symposium on Logical Foundations of Computer Science, LFCS 2020

Y2 - 4 January 2020 through 7 January 2020

ER -

Von denselben Autoren