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
Parameterized complexity of abduction in Schaefer's framework
Leibniz Univ Hannover, Inst Theoret Informat, Appelstr 4, D-30167 Hannover, Germany..
Leibniz Univ Hannover, Inst Theoret Informat, Appelstr 4, D-30167 Hannover, Germany..
Jönköping University, School of Engineering, JTH, Department of Computer Science and Informatics.
2021 (English)In: Journal of logic and computation (Print), ISSN 0955-792X, E-ISSN 1465-363X, Vol. 31, no 1, p. 266-296Article in journal (Refereed) Published
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 the problem of wether there exists a set of explanations, two explanation size limited variants of this reasoning problem (less than or equal to, and equal to a given size bound). In this paper, we present a thorough two-dimensional classification of these problems: the first dimension is regarding the parameterized complexity under a wealth of different parameterizations, and the second dimension spans through all possible Boolean fragments of these problems in Schaefer's constraint satisfaction framework with co-clones (T. J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, R.J. Lipton, W.A. Burkhard, W.J. Savitch, E.P. Friedman, A.V. Aho eds, pp. 216-226. ACM, 1978). Thereby, we almost complete the parameterized complexity classification program initiated by Fellows et al. (The parameterized complexity of abduction. In Proceedings of the Twenty-Sixth AAAI Conference on Articial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada, J. Homann, B. Selman eds. AAAI Press, 2012), partially building on the results by Nordh and Zanuttini (What makes propositional abduction tractable. Artificial Intelligence, 172, 1245-1284, 2008). In this process, we outline a fine-grained analysis of the inherent parameterized 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
Oxford University Press, 2021. Vol. 31, no 1, p. 266-296
Keywords [en]
Parameterized complexity, abduction, non-monotonic reasoning, Schaefer's framework, co-clones
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:hj:diva-53065DOI: 10.1093/logcom/exaa079ISI: 000648960600012Scopus ID: 2-s2.0-85126950043Local ID: ;intsam;747466OAI: oai:DiVA.org:hj-53065DiVA, id: diva2:1564141
Available from: 2021-06-11 Created: 2021-06-11 Last updated: 2022-04-06Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Schmidt, Johannes

Search in DiVA

By author/editor
Schmidt, Johannes
By organisation
JTH, Department of Computer Science and Informatics
In the same journal
Journal of logic and computation (Print)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 108 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