Details
| Original language | English |
|---|---|
| Title of host publication | Logical Foundations of Computer Science (LFCS 2020) |
| Subtitle of host publication | International Symposium, LFCS 2020, Proceedings |
| Editors | Sergei Artemov, Anil Nerode |
| Place of Publication | Cham |
| Pages | 195-213 |
| Number of pages | 19 |
| ISBN (electronic) | 978-3-030-36755-8 |
| Publication status | Published - 2020 |
| Event | International Symposium on Logical Foundations of Computer Science, LFCS 2020 - Deerfield Beach, United States Duration: 4 Jan 2020 → 7 Jan 2020 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 11972 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 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.
Keywords
- Abduction, Co-clones, Parameterised complexity, Schaefer’s framework
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Logical Foundations of Computer Science (LFCS 2020): International Symposium, LFCS 2020, Proceedings. ed. / Sergei Artemov; Anil Nerode. Cham, 2020. p. 195-213 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11972 LNCS).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
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 -