Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Parameterised Complexity of Abduction in Schaefer’s Framework
Institut für Theoretische Informatik, Leibniz Universität Hannover, Hanover, Germany.
Institut für Theoretische Informatik, Leibniz Universität Hannover, Hanover, Germany.
Jönköping University, School of Engineering, JTH, Computer Science and Informatics.
2020 (English)In: Logical Foundations of Computer Science: International Symposium, LFCS 2020, Deerfield Beach, FL, USA, January 4–7, 2020 Proceedings / [ed] Artemov S., Nerode A., Cham: Springer, 2020, p. 195-213Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Cham: Springer, 2020. p. 195-213
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 11972
Keywords [en]
Abduction, Co-clones, Parameterised complexity, Schaefer’s framework, Algebra, Cloning, Cobalt compounds, Parameterization, Abductive reasoning, Algebraic approaches, Constraint Satisfaction, Fine-grained analysis, Reasoning problems, Constraint satisfaction problems
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:hj:diva-47488DOI: 10.1007/978-3-030-36755-8_13Scopus ID: 2-s2.0-85077493558ISBN: 9783030367541 (print)ISBN: 978-3-030-36755-8 (electronic)OAI: oai:DiVA.org:hj-47488DiVA, id: diva2:1387724
Conference
International Symposium, LFCS 2020 Deerfield Beach, FL, USA, January 4–7, 2020
Available from: 2020-01-22 Created: 2020-01-22 Last updated: 2020-01-23Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Schmidt, Johannes

Search in DiVA

By author/editor
Schmidt, Johannes
By organisation
JTH, Computer Science and Informatics
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 17 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf