{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T01:30:48Z","timestamp":1785202248697,"version":"3.55.0"},"reference-count":44,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2020,12,29]],"date-time":"2020-12-29T00:00:00Z","timestamp":1609200000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"publisher","award":["ME4279\/1-2"],"award-info":[{"award-number":["ME4279\/1-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,1,22]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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\u2019s 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\u20133, 1978, San Diego, California, USA, R.J. Lipton, W.A. Burkhard, W.J. Savitch, E.P. Friedman, A.V. Aho eds, pp. 216\u2013226. 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\u201326, 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\u20131284, 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.<\/jats:p>","DOI":"10.1093\/logcom\/exaa079","type":"journal-article","created":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T04:51:24Z","timestamp":1607489484000},"page":"266-296","source":"Crossref","is-referenced-by-count":4,"title":["Parameterized complexity of abduction in Schaefer\u2019s framework"],"prefix":"10.1093","volume":"31","author":[{"given":"Yasir","family":"Mahmood","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik, Leibniz Universit\u00e4t Hannover, Appelstra\u00dfe 4, 30167 Hannover, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arne","family":"Meier","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik, Leibniz Universit\u00e4t Hannover, Appelstra\u00dfe 4, 30167 Hannover, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johannes","family":"Schmidt","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Informatics, School of Engineering, J\u00f6nk\u00f6ping University, Gjuterigatan 5, 55111, J\u00f6nk\u00f6ping, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2020,12,29]]},"reference":[{"key":"2021032411475774700_ref1","doi-asserted-by":"crossref","first-page":"13:1","DOI":"10.1145\/1877714.1877719","article-title":"The tractability of model checking for LTL: the good, the bad, and the ugly fragments","volume":"12","author":"Bauland","year":"2011","journal-title":"ACM Transactions on Computational Logic (TOCL)"},{"key":"2021032411475774700_ref2","doi-asserted-by":"crossref","DOI":"10.2168\/LMCS-5(1:1)2009","article-title":"The complexity of generalized satisfiability for linear temporal logic","volume":"5","author":"Bauland","year":"2009","journal-title":"Logical Methods in Computer Science"},{"key":"2021032411475774700_ref3","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1093\/logcom\/exq061","article-title":"The complexity of reasoning for fragments of default logic","volume":"22","author":"Beyersdorff","year":"2012","journal-title":"Journal of Logic and Computation"},{"key":"2021032411475774700_ref4","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.ipl.2005.06.003","article-title":"Bases for boolean co-clones","volume":"96","author":"B\u00f6hler","year":"2005","journal-title":"Information Processing Letters"},{"key":"2021032411475774700_ref5","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1051\/ita\/2016022","article-title":"Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems","volume":"50","author":"Bonnet","year":"2016","journal-title":"RAIRO\u2014Theoretical Informatics and Applications"},{"key":"2021032411475774700_ref6","doi-asserted-by":"crossref","first-page":"19:1","DOI":"10.1145\/2629421","article-title":"Complexity classifications for logic-based argumentation","volume":"15","author":"Creignou","year":"2014","journal-title":"ACM Transactions on Computational Logic"},{"key":"2021032411475774700_ref7","doi-asserted-by":"crossref","DOI":"10.3390\/a12090189","article-title":"Parameterised enumeration for modification problems","volume":"12","author":"Creignou","year":"2019","journal-title":"Algorithms"},{"key":"2021032411475774700_ref8","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1007\/s00224-016-9702-4","article-title":"Paradigms for parameterized enumeration","volume":"60","author":"Creignou","year":"2017","journal-title":"Theory of Computing Systems"},{"key":"2021032411475774700_ref9","doi-asserted-by":"crossref","first-page":"17:1","DOI":"10.1145\/2159531.2159539","article-title":"The complexity of reasoning for fragments of autoepistemic logic","volume":"13","author":"Creignou","year":"2012","journal-title":"ACM Transactions on Computational Logic"},{"key":"2021032411475774700_ref10","first-page":"120","article-title":"Enumerating all solutions of a boolean CSP by non-decreasing weight","volume-title":"Theory and Applications of Satisfiability Testing\u2014SAT 2011\u201414th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19\u201322, 2011. Proceedings","author":"Creignou","year":"2011"},{"key":"2021032411475774700_ref11","article-title":"Complexity of propositional abduction for restricted sets of boolean functions","volume-title":"Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference","author":"Creignou","year":"2010"},{"key":"2021032411475774700_ref12","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1093\/logcom\/exr012","article-title":"Complexity classifications for propositional abduction in post\u2019s framework","volume":"22","author":"Creignou","year":"2012","journal-title":"Journal of Logic and Computation"},{"key":"2021032411475774700_ref13","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/978-3-642-15675-5_12","article-title":"Sets of boolean connectives that make argumentation easier","volume-title":"Proc. 12th European Conference on Logics in Artificial Intelligence","author":"Creignou","year":"2010"},{"key":"2021032411475774700_ref14","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1080\/19462166.2011.629736","article-title":"Complexity of logic-based argumentation in post\u2019s framework","volume":"2","author":"Creignou","year":"2011","journal-title":"Argument & Computation"},{"key":"2021032411475774700_ref15","first-page":"3","article-title":"Boolean constraint satisfaction problems: when does post\u2019s lattice help?","volume-title":"Complexity of Constraints\u2014An Overview of Current Research Themes [Result of a Dagstuhl Seminar]","author":"Creignou","year":"2008"},{"key":"2021032411475774700_ref16","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1137\/S0097539704446311","article-title":"A complete classification of the complexity of propositional abduction","volume":"36","author":"Creignou","year":"2006","journal-title":"SIAM Journal on Computing"},{"key":"2021032411475774700_ref17","article-title":"Monographs in Computer Science","volume-title":"Parameterized Complexity","author":"Downey","year":"1999"},{"key":"2021032411475774700_ref18","article-title":"Texts in Computer Science","volume-title":"Fundamentals of Parameterized Complexity","author":"Downey","year":"2013"},{"key":"2021032411475774700_ref19","first-page":"451","article-title":"The Inference Problem for Propositional Circumscription of Affine Formulas Is coNP-Complete","volume-title":"STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27\u2013March 1, 2003, Proceedings","author":"Durand","year":"2003"},{"key":"2021032411475774700_ref20","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/200836.200838","article-title":"The complexity of logic-based abduction","volume":"42","author":"Eiter","year":"1995","journal-title":"Journal of the ACM"},{"key":"2021032411475774700_ref21","article-title":"The parameterized complexity of abduction","volume-title":"Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence","author":"Fellows","year":"2012"},{"key":"2021032411475774700_ref22","article-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"Flum","year":"2006"},{"key":"2021032411475774700_ref23","first-page":"1","article-title":"Generalized modal satisfiability","author":"Hemaspaandra","year":"2008"},{"key":"2021032411475774700_ref24","first-page":"445","article-title":"A mechanism for forming composite explanatory hypotheses","volume-title":"IEEE Systems, Man, and Cybernetics","author":"Josephson","year":"1987"},{"key":"2021032411475774700_ref25","first-page":"85","article-title":"Reducibility among combinatorial problems","volume-title":"Proceedings of a Symposium on the Complexity of Computer Computations, held March 20\u201322, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series","author":"Karp","year":"1972"},{"key":"2021032411475774700_ref26","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF01744287","article-title":"Satisfiability problems for propositional calculi","volume":"13","author":"Lewis","year":"1979","journal-title":"Mathematical Systems Theory"},{"key":"2021032411475774700_ref27","first-page":"587","article-title":"The complexity of satisfiability for fragments of hybrid logic\u2014Part I","volume":"5734","author":"Meier","year":"2009","journal-title":"Proc. MFCS. LNCS"},{"key":"2021032411475774700_ref28","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.tcs.2013.02.009","article-title":"Generalized satisfiability for the description logic ALC","volume":"505","author":"Meier","year":"2013","journal-title":"Theoretical Computer Science"},{"key":"2021032411475774700_ref29","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1142\/S0129054109006954","article-title":"The complexity of satisfiability for fragments of CTL and ctl$\\ast $","volume":"20","author":"Meier","year":"2009","journal-title":"International Journal of Foundations of Computer Science"},{"key":"2021032411475774700_ref30","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0004-3702(71)90009-9","article-title":"Hypothesis generation by machine","volume":"2","author":"Morgan","year":"1971","journal-title":"Artificial Intelligence"},{"key":"2021032411475774700_ref31","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1016\/j.artint.2008.02.001","article-title":"What makes propositional abduction tractable","volume":"172","author":"Nordh","year":"2008","journal-title":"Artificial Intelligence"},{"key":"2021032411475774700_ref32","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"O\u2019Donnell","year":"2014"},{"key":"2021032411475774700_ref33","author":"Papadimitriou","year":"1994","journal-title":"Computational Complexity"},{"key":"2021032411475774700_ref34","volume-title":"Collected Papers of Charles Sanders Peirce","author":"Peirce","year":"1958"},{"key":"2021032411475774700_ref35","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-8682-5","article-title":"Artificial Intelligence","volume-title":"Abductive Inference Models for Diagnostic Problem-Solving","author":"Peng","year":"1990"},{"key":"2021032411475774700_ref36","first-page":"1304","article-title":"Normality and faults in logic-based diagnosis","volume-title":"Proceedings of the 11th International Joint Conference on Artificial Intelligence","author":"Poole","year":"1989"},{"key":"2021032411475774700_ref37","first-page":"1","article-title":"The two-valued iterative systems of mathematical logic","volume":"5","author":"Post","year":"1941","journal-title":"Annals of Mathematical Studies"},{"key":"2021032411475774700_ref38","article-title":"Generalized satisfiability problems","author":"Reith","year":"2001"},{"key":"2021032411475774700_ref39","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","article-title":"Graph minors. II. Algorithmic aspects of tree-width","volume":"7","author":"Robertson","year":"1986","journal-title":"Journal of Algorithms"},{"key":"2021032411475774700_ref40","first-page":"216","article-title":"The complexity of satisfiability problems","volume-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing","author":"Schaefer","year":"1978"},{"key":"2021032411475774700_ref41","first-page":"229","article-title":"Partial polymorphisms and constraint satisfaction problems","volume-title":"Complexity of Constraints\u2014An Overview of Current Research Themes [Result of a Dagstuhl Seminar]","author":"Schnoor","year":"2008"},{"key":"2021032411475774700_ref42","first-page":"343","article-title":"Abductive and default reasoning: a computational core","volume-title":"Proceedings of the 8th National Conference on Artificial Intelligence","author":"Selman","year":"1990"},{"key":"2021032411475774700_ref43","author":"Sipser","year":"1997","journal-title":"Introduction to the Theory of Computation"},{"key":"2021032411475774700_ref44","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-3-642-04238-6_25","article-title":"The complexity of circumscriptive inference in post\u2019s lattice","volume-title":"Proc. 10th International Conference on Logic Programming and Nonmonotonic Reasoning","author":"Thomas","year":"2009"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/31\/1\/266\/36677493\/exaa079.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/31\/1\/266\/36677493\/exaa079.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,24]],"date-time":"2021-03-24T11:49:03Z","timestamp":1616586543000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/31\/1\/266\/6049828"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,29]]},"references-count":44,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,12,29]]},"published-print":{"date-parts":[[2021,1,22]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exaa079","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,1]]},"published":{"date-parts":[[2020,12,29]]}}}