{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:01:53Z","timestamp":1750309313083,"version":"3.41.0"},"reference-count":97,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T00:00:00Z","timestamp":1718582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["ME 4279\/1-1"],"award-info":[{"award-number":["ME 4279\/1-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2024,7,31]]},"abstract":"<jats:p>In this article, we introduce a notion of backdoors to Reiter\u2019s propositional default logic and study structural properties of it. Also we consider the problems of backdoor detection (parameterised by the solution size) as well as backdoor evaluation (parameterised by the size of the given backdoor) for various kinds of target classes (CNF, KROM, MONOTONE) and all SCHAEFER classes. Also, we study generalisations of HORN-formulas, namely QHORN, RHORN, as well as DUALHORN. For these classes, we also classify the computational complexity of the implication problem. We show that backdoor detection is fixed-parameter tractable for the considered target classes and prove a complete trichotomy for backdoor evaluation. The problems are either fixed-parameter tractable, para-DeltaP2-complete, or para-NP-complete, depending on the target class.<\/jats:p>","DOI":"10.1145\/3655024","type":"journal-article","created":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T09:24:05Z","timestamp":1711790645000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Strong Backdoors for Default Logic"],"prefix":"10.1145","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8681-7470","authenticated-orcid":false,"given":"Johannes Klaus","family":"Fichte","sequence":"first","affiliation":[{"name":"Link\u00f6ping University, Link\u00f6ping, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8061-5376","authenticated-orcid":false,"given":"Arne","family":"Meier","sequence":"additional","affiliation":[{"name":"Leibniz Universit\u00e4t Hannover, Hannover, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-0948-167X","authenticated-orcid":false,"given":"Irena","family":"Schindler","sequence":"additional","affiliation":[{"name":"independent researcher, Garbsen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,17]]},"reference":[{"issue":"5","key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1017\/S1471068417000278","article-title":"Model enumeration in propositional circumscription via unsatisfiable core analysis","volume":"17","author":"Alviano Mario","year":"2017","unstructured":"Mario Alviano. 2017. Model enumeration in propositional circumscription via unsatisfiable core analysis. Theory Pract. Log. Program. 17, 5-6 (2017), 708\u2013725.","journal-title":"Theory Pract. Log. Program."},{"key":"e_1_3_2_3_2","first-page":"1669","volume-title":"Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI\u201918)","author":"Alviano Mario","year":"2018","unstructured":"Mario Alviano. 2018. Query answering in propositional circumscription. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI\u201918), J\u00e9r\u00f4me Lang (Ed.). 1669\u20131675."},{"issue":"1","key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1016\/S0304-3975(01)00383-8","article-title":"Propositional default logics made easier: Computational complexity of model checking","volume":"289","author":"Baumgartner Robert","year":"2002","unstructured":"Robert Baumgartner and Georg Gottlob. 2002. Propositional default logics made easier: Computational complexity of model checking. Theor. Comput. Sci. 289, 1 (2002), 591\u2013627.","journal-title":"Theor. Comput. Sci."},{"key":"e_1_3_2_5_2","first-page":"302","volume-title":"Proceedings of the 9th International Workshop on Non-Monotonic Reasoning (NMR\u201902)","author":"Berzati Dritan","year":"2002","unstructured":"Dritan Berzati, Bernhard Anrig, and J\u00fcrg Kohlas. 2002. Embedding default logic in propositional argumentation systems. In Proceedings of the 9th International Workshop on Non-Monotonic Reasoning (NMR\u201902), Salem Benferhat and Enrico Giunchiglia (Eds.). 302\u2013310."},{"issue":"7","key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1007\/s00153-011-0245-8","article-title":"Proof complexity of propositional default logic","volume":"50","author":"Beyersdorff Olaf","year":"2011","unstructured":"Olaf Beyersdorff, Arne Meier, Sebastian M\u00fcller, Michael Thomas, and Heribert Vollmer. 2011. Proof complexity of propositional default logic. Arch. Math. Log. 50, 7-8 (2011), 727\u2013742.","journal-title":"Arch. Math. Log."},{"issue":"18","key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"1071","DOI":"10.1016\/j.ipl.2009.06.015","article-title":"The complexity of propositional implication","volume":"109","author":"Beyersdorff Olaf","year":"2009","unstructured":"Olaf Beyersdorff, Arne Meier, Michael Thomas, and Heribert Vollmer. 2009. The complexity of propositional implication. Inform. Process. Lett. 109, 18 (2009), 1071\u20131077.","journal-title":"Inform. Process. Lett."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exq061"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01531068"},{"issue":"1","key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(94)90033-7","article-title":"Recognition of q-Horn formulae in linear time","volume":"55","author":"Boros Endre","year":"1994","unstructured":"Endre Boros, Peter L. Hammer, and Xiaorong Sun. 1994. Recognition of q-Horn formulae in linear time. Discr. Appl. Math. 55, 1 (1994), 1\u201313.","journal-title":"Discr. Appl. Math."},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF01531069","article-title":"On renamable horn and generalized horn functions","volume":"1","author":"Chandru V.","year":"1990","unstructured":"V. Chandru, Collette R. Coullard, Peter L. Hammer, M. Montanuz, and Xiaorong Sun. 1990. On renamable horn and generalized horn functions. Ann. Math. Artif. Intell. 1 (1990), 33\u201347.","journal-title":"Ann. Math. Artif. Intell."},{"issue":"2","key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","article-title":"Tight lower bounds for certain parameterized NP-hard problems","volume":"201","author":"Chen Jianer","year":"2005","unstructured":"Jianer Chen, Benny Chor, Michael R. Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanji, and Ge Xia. 2005. Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201, 2 (2005), 216\u2013231.","journal-title":"Inf. Comput."},{"key":"e_1_3_2_13_2","first-page":"193","volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle Bruno","year":"1990","unstructured":"Bruno Courcelle. 1990. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science, Jan van Leeuwen (Ed.). Vol. Formal Models and Semantics. MIT Press, Cambridge, MA, 193\u2013242."},{"key":"e_1_3_2_14_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-order Logic, a Language Theoretic Approach","author":"Courcelle Bruno","year":"2012","unstructured":"Bruno Courcelle and Joost Engelfriet. 2012. Graph Structure and Monadic Second-order Logic, a Language Theoretic Approach. Cambridge University Press, Cambridge, UK."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.3390\/a12090189"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9702-4"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2159531.2159539"},{"key":"e_1_3_2_18_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-319-09284-3_8","volume-title":"Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201914),","volume":"8561","author":"DeHaan Ronald","year":"2014","unstructured":"Ronald DeHaan and Stefan Szeider. 2014. Fixed-parameter tractable reductions to SAT. In Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201914),Lecture Notes in Computer Science, Vol. 8561, Carsten Sinz and Uwe Egly (Eds.). Springer Verlag, Vienna, Austria, 85\u2013102. DOI:10.1007\/978-3-319-09284-3_8"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/11847250_11","volume-title":"Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC\u201906)","author":"Downey Rodney G.","year":"2006","unstructured":"Rodney G. Downey, Michael R. Fellows, and Catherine McCartin. 2006. Parameterized approximation problems. In Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC\u201906), Hans L. Bodlaender and Michael A. Langston (Eds.). Springer Verlag, 121\u2013129. DOI:10.1007\/11847250_11"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.03.002"},{"key":"e_1_3_2_23_2","first-page":"417","volume-title":"Proceedings of the 17th Conference on Artificial Intelligence (AAAI\u201900)","author":"Egly Uwe","year":"2000","unstructured":"Uwe Egly, Thomas Eiter, Hans Tompits, and Stefan Woltran. 2000. Solving advanced reasoning tasks using quantified boolean formulas. In Proceedings of the 17th Conference on Artificial Intelligence (AAAI\u201900), Henry Kautz and Bruce Porter (Eds.). The AAAI Press, Austin, TX, 417\u2013422."},{"key":"e_1_3_2_24_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BFb0036168","volume-title":"Proceedings of the 11th International Symposium on Fundamentals of Computation Theory (FCT\u201997),","volume":"1279","author":"Eiter Thomas","year":"1997","unstructured":"Thomas Eiter and Georg Gottlob. 1997. The complexity class \\(\\Theta ^ \\mathrm{P}_2\\) : Recent results and applications in AI and modal logic. In Proceedings of the 11th International Symposium on Fundamentals of Computation Theory (FCT\u201997),Lecture Notes in Computer Science, Vol. 1279, Bogdan S. Chlebus and Ludwik Czaja (Eds.). Springer Verlag, 1\u201318. DOI:10.1007\/BFb0036168"},{"key":"e_1_3_2_25_2","first-page":"489","volume-title":"Proceedings of the 10th International Joint Conference on Artificial Intelligence (IJCAI\u201987)","author":"Etherington David W.","year":"1987","unstructured":"David W. Etherington. 1987. Relating default logic and circumscription. In Proceedings of the 10th International Joint Conference on Artificial Intelligence (IJCAI\u201987), John McDermott (Ed.). Morgan Kaufmann, Milan, Italy, 489\u2013494."},{"key":"e_1_3_2_26_2","first-page":"6312","volume-title":"Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI\u201921)","volume":"35","author":"Fandinno Jorge","year":"2021","unstructured":"Jorge Fandinno and Markus Hecher. 2021. Treewidth-aware complexity in ASP: Not all positive cycles are equally hard. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI\u201921), Kevin Leyton-Brown and Mausam (Eds.), Vol. 35. 6312\u20136320. DOI:10.1609\/aaai.v35i7.16784"},{"key":"e_1_3_2_27_2","first-page":"1880","volume-title":"Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI\u201921)","author":"Fichte Johannes","year":"2021","unstructured":"Johannes Fichte, Markus Hecher, Yasir Mahmood, and Arne Meier. 2021. Decomposition-guided reductions for argumentation and treewidth. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI\u201921), Zhi-Hua Zhou (Ed.). International Joint Conferences on Artificial Intelligence Organization, 1880\u20131886. DOI:10.24963\/ijcai.2021\/259"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3560469"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i5.20506"},{"key":"e_1_3_2_30_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-3-030-20528-7_9","volume-title":"Proceedings of the 15th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201919),","volume":"11481","author":"Fichte Johannes Klaus","year":"2019","unstructured":"Johannes Klaus Fichte and Markus Hecher. 2019. Treewidth and counting projected answer sets. In Proceedings of the 15th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201919),Lecture Notes in Computer Science, Vol. 11481, Marcello Balduccini, Yuliya Lierler, and Stefan Woltran (Eds.). Springer Verlag, 105\u2013119. DOI:10.1007\/978-3-030-20528-7_9"},{"key":"e_1_3_2_31_2","first-page":"2827","volume-title":"Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI\u201919)","author":"Fichte Johannes Klaus","year":"2019","unstructured":"Johannes Klaus Fichte, Markus Hecher, and Arne Meier. 2019. Counting complexity for reasoning in abstract argumentation. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI\u201919). The AAAI Press, 2827\u20132834. DOI:10.1609\/aaai.v33i01.33012827"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i7.16788"},{"key":"e_1_3_2_33_2","first-page":"2620","volume-title":"Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI\u201922)","author":"Fichte Johannes K.","year":"2022","unstructured":"Johannes K. Fichte, Markus Hecher, and Mohamed A. Nadeem. 2022. Plausibility reasoning via projected answer set counting\u2014A hybrid approach. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI\u201922), Lud De Raedt (Ed.). International Joint Conferences on Artificial Intelligence Organization, 2620\u20132626. DOI:10.24963\/ijcai.2022\/363"},{"key":"e_1_3_2_34_2","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 12th International Conference on Language and Automata Theory and Applications (LATA\u201918),","author":"Fichte Johannes K.","year":"2018","unstructured":"Johannes K. Fichte, Markus Hecher, and Irina Schindler. 2018. Default logic and bounded treewidth. In Proceedings of the 12th International Conference on Language and Automata Theory and Applications (LATA\u201918),Lecture Notes in Computer Science, Shmuel Tomi Klein and Carlos Mart\u00edn-Vide (Eds.). Springer Verlag."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.IC.2020.104675"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-019-09633-x"},{"key":"e_1_3_2_37_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/978-3-319-40970-2_4","volume-title":"Proceedings of the 19th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201916),","volume":"9710","author":"Fichte Johannes Klaus","year":"2016","unstructured":"Johannes Klaus Fichte, Arne Meier, and Irina Schindler. 2016. Strong backdoors for default logic. In Proceedings of the 19th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201916),Lecture Notes in Computer Science, Vol. 9710, Nadia Creignou and Daniel Le Berre (Eds.). Springer Verlag, 45\u201359. DOI:10.1007\/978-3-319-40970-2_4"},{"issue":"1","key":"e_1_3_2_38_2","first-page":"7","article-title":"Backdoors to normality for disjunctive logic programs","volume":"17","author":"Fichte Johannes K.","year":"2015","unstructured":"Johannes K. Fichte and Stefan Szeider. 2015. Backdoors to normality for disjunctive logic programs. ACM Trans. Comput. Log. 17, 1 (2015), 7.","journal-title":"ACM Trans. Comput. Log."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.12.001"},{"issue":"2","key":"e_1_3_2_40_2","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/S0890-5401(03)00161-5","article-title":"Describing parameterized complexity classes","volume":"187","author":"Flum J\u00f6rg","year":"2003","unstructured":"J\u00f6rg Flum and Martin Grohe. 2003. Describing parameterized complexity classes. Inf. Comput. 187, 2 (2003), 291\u2013319.","journal-title":"Inf. Comput."},{"key":"e_1_3_2_41_2","series-title":"Theoretical Computer Science","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","year":"2006","unstructured":"J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Theoretical Computer Science, Vol. XIV. Springer Verlag, Berlin. DOI:10.1007\/3-540-29953-X"},{"key":"e_1_3_2_42_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/978-3-319-66263-3_2","volume-title":"Proceedings of the 20th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201917),","volume":"10491","author":"Ganian Robert","year":"2017","unstructured":"Robert Ganian, M. S. Ramanujan, and Stefan Szeider. 2017. Backdoor treewidth for SAT. In Proceedings of the 20th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201917),Lecture Notes in Computer Science, Vol. 10491, Serge Gaspers and Toby Walsh (Eds.). Springer Verlag, 20\u201337. DOI:10.1007\/978-3-319-66263-3_2"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.10.007"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9958-5"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.4230\/DFU.Vol7.15301.137"},{"key":"e_1_3_2_46_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/978-3-642-30891-8_15","volume-title":"The Multivariate Algorithmic Revolution and Beyond\u2014Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday","author":"Gaspers Serge","year":"2012","unstructured":"Serge Gaspers and Stefan Szeider. 2012. Backdoors to satisfaction. In The Multivariate Algorithmic Revolution and Beyond\u2014Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, Vol. 7370, Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and D\u00e1niel Marx (Eds.). Springer Verlag, 287\u2013317."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/2.3.397"},{"issue":"4","key":"e_1_3_2_48_2","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1145\/210332.210334","article-title":"Translating default logic into standard autoepistemic logic","volume":"42","author":"Gottlob Georg","year":"1995","unstructured":"Georg Gottlob. 1995. Translating default logic into standard autoepistemic logic. J. ACM 42, 4 (1995), 711\u2013740.","journal-title":"J. ACM"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2009.10.003"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00182-0"},{"issue":"3","key":"e_1_3_2_51_2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1093\/comjnl\/bxm056","article-title":"Fixed-parameter algorithms for artificial intelligence, constraint satisfaction, and database problems","volume":"51","author":"Gottlob Georg","year":"2006","unstructured":"Georg Gottlob and Stefan Szeider. 2006. Fixed-parameter algorithms for artificial intelligence, constraint satisfaction, and database problems. Comput. J. 51, 3 (2006), 303\u2013325. Survey paper.","journal-title":"Comput. J."},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103651"},{"key":"e_1_3_2_53_2","first-page":"1286","volume-title":"Proceedings of the 25h International Joint Conference on Artificial Intelligence (IJCAI\u201916)","author":"Hertum Pieter Van","year":"2016","unstructured":"Pieter Van Hertum, Marcos Cramer, Bart Bogaerts, and Marc Denecker. 2016. Distributed autoepistemic logic and its application to access control. In Proceedings of the 25h International Joint Conference on Artificial Intelligence (IJCAI\u201916), Gerhard Brewka (Ed.). IJCAI\/AAAI Press, New York, NY, 1286\u20131292."},{"issue":"1","key":"e_1_3_2_54_2","doi-asserted-by":"crossref","first-page":"14","DOI":"10.2307\/2268661","article-title":"On sentences which are true of direct unions of algebras","volume":"16","author":"Horn Alfred","year":"1951","unstructured":"Alfred Horn. 1951. On sentences which are true of direct unions of algebras. J. Symb. Log. 16, 1 (1951), 14\u201321.","journal-title":"J. Symb. Log."},{"issue":"1","key":"e_1_3_2_55_2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1023\/A:1018915113814","article-title":"On the intertranslatability of non-monotonic logics","volume":"27","author":"Janhunen Tomi","year":"1999","unstructured":"Tomi Janhunen. 1999. On the intertranslatability of non-monotonic logics. Ann. Math. Artif. Intell. 27, 1-4 (1999), 79\u2013128.","journal-title":"Ann. Math. Artif. Intell."},{"key":"e_1_3_2_56_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01683259","article-title":"New problems complete for nondeterministic loc space","volume":"10","author":"Jones Neil D.","year":"1976","unstructured":"Neil D. Jones, Y. Edmund Lien, and William T. Laaser. 1976. New problems complete for nondeterministic loc space. Math. Syst. Theory 10 (1976), 1\u201317.","journal-title":"Math. Syst. Theory"},{"key":"e_1_3_2_57_2","series-title":"CEUR Workshop Proceedings","volume-title":"Description Logics","volume":"2211","author":"Kiesel Rafael","year":"2018","unstructured":"Rafael Kiesel, Erman Acar, and Stefan Schlobach. 2018. Preferential default reasoning on the semantic web. In Description Logics(CEUR Workshop Proceedings, Vol. 2211). CEUR-WS.org."},{"issue":"3","key":"e_1_3_2_58_2","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0004-3702(88)90021-5","article-title":"On the relation between default and autoepistemic logic","volume":"35","author":"Konolige Kurt","year":"1988","unstructured":"Kurt Konolige. 1988. On the relation between default and autoepistemic logic. Artif, Intell, 35, 3 (1988), 343\u2013382.","journal-title":"Artif, Intell,"},{"issue":"9","key":"e_1_3_2_59_2","first-page":"092107:1\u2013092107","article-title":"The propositional normal default logic and the finite\/infinite injury priority method","volume":"60","author":"Li Wei","year":"2017","unstructured":"Wei Li, Yuefei Sui, and Yuhui Wang. 2017. The propositional normal default logic and the finite\/infinite injury priority method. Sci. China Inf. Sci. 60, 9 (2017), 092107:1\u2013092107:10.","journal-title":"Sci. China Inf. Sci."},{"issue":"2","key":"e_1_3_2_60_2","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.datak.2005.03.002","article-title":"The complexity of model checking for propositional default logics","volume":"55","author":"Liberatore Paolo","year":"2005","unstructured":"Paolo Liberatore and Marco Schaerf. 2005. The complexity of model checking for propositional default logics. Data Knowl. Eng. 55, 2 (2005), 189\u2013202.","journal-title":"Data Knowl. Eng."},{"key":"e_1_3_2_61_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/978-3-030-36755-8_13","volume-title":"Proceedings of the International Symposium on Logical Foundations of Computer Science (LFCS\u201920),","volume":"11972","author":"Mahmood Yasir","year":"2020","unstructured":"Yasir Mahmood, Arne Meier, and Johannes Schmidt. 2020. Parameterised complexity of abduction in schaefer\u2019s framework. In Proceedings of the International Symposium on Logical Foundations of Computer Science (LFCS\u201920),Lecture Notes in Computer Science, Vol. 11972, Sergei N. Art\u00ebmov and Anil Nerode (Eds.). Springer, 195\u2013213. DOI:10.1007\/978-3-030-36755-8_13"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1093\/LOGCOM\/EXAA079"},{"key":"e_1_3_2_63_2","first-page":"276","volume-title":"Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning (KR\u201989)","author":"Marek V. Wiktor","year":"1989","unstructured":"V. Wiktor Marek and Miroslaw Truszczynski. 1989. Relating autoepistemic and default logics. In Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning (KR\u201989). Morgan Kaufmann, 276\u2013288."},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02906-0"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(80)90011-9"},{"issue":"1","key":"e_1_3_2_66_2","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0004-3702(80)90011-9","article-title":"Circumscription\u2014A form of non-monotonic reasoning","volume":"13","author":"McCarthy J.","year":"1980","unstructured":"J. McCarthy. 1980. Circumscription\u2014A form of non-monotonic reasoning. Artif. Intell. 13, 1-2 (1980), 27\u201339.","journal-title":"Artif. Intell."},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(80)90012-0"},{"issue":"1","key":"e_1_3_2_68_2","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/322290.322293","article-title":"Nonmonotonic logic II: Nonmonotonic modal theories","volume":"29","author":"McDermott Drew V.","year":"1982","unstructured":"Drew V. McDermott. 1982. Nonmonotonic logic II: Nonmonotonic modal theories. J. ACM 29, 1 (1982), 33\u201357.","journal-title":"J. ACM"},{"issue":"1","key":"e_1_3_2_69_2","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0004-3702(80)90012-0","article-title":"Non-monotonic logic I","volume":"13","author":"McDermott Drew V.","year":"1980","unstructured":"Drew V. McDermott and Jon Doyle. 1980. Non-monotonic logic I. Artif. Intell. 13, 1-2 (1980), 41\u201372.","journal-title":"Artif. Intell."},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.3390\/a13050122"},{"key":"e_1_3_2_71_2","volume-title":"Parametrised Enumeration","author":"Meier Arne","year":"2020","unstructured":"Arne Meier. 2020. Parametrised Enumeration. Habilitation thesis, Leibniz Universit\u00e4t Hannover."},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0515-5"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-015-0435-x"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00153-015-0435-X"},{"key":"e_1_3_2_75_2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0004-3702(85)90042-6","article-title":"Semantical considerations on modal logic","volume":"25","author":"Moore Robert C.","year":"1985","unstructured":"Robert C. Moore. 1985. Semantical considerations on modal logic. Artif. Intell. 25, 1 (Jan.1985), 75\u201394.","journal-title":"Artif. Intell."},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(85)90042-6"},{"key":"e_1_3_2_77_2","series-title":"Lecture Notes in Computer Science","first-page":"96","volume-title":"Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201904),","volume":"3542","author":"Nishimura Naomi","year":"2004","unstructured":"Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider. 2004. Detecting backdoor sets with respect to horn and binary clauses. In Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201904),Lecture Notes in Computer Science, Vol. 3542, Holger H. Hoos and David G. Mitchell (Eds.). Springer Verlag, Vancouver, BC, Canada, 96\u2013103."},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.12.039"},{"key":"e_1_3_2_79_2","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","year":"1994","unstructured":"Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley."},{"key":"e_1_3_2_80_2","volume-title":"Collected Papers of Charles Sanders Peirce","author":"Peirce Charles Sanders","year":"1958","unstructured":"Charles Sanders Peirce. 1958. Collected Papers of Charles Sanders Peirce. Oxford University Press."},{"key":"e_1_3_2_81_2","volume-title":"The Collected Papers of Charles Sanders Peirce","author":"Peirce C. S.","year":"1932","unstructured":"C. S. Peirce, C. Hartshorne, and P. Weiss. 1932. The Collected Papers of Charles Sanders Peirce. Cambridge University Press, Cambridge."},{"key":"e_1_3_2_82_2","first-page":"1046","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI\u201913)","author":"Pfandler Andreas","year":"2013","unstructured":"Andreas Pfandler, Stefan R\u00fcmmele, and Stefan Szeider. 2013. Backdoors to abduction. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI\u201913), Francesca Rossi (Ed.). The AAAI Press, 1046\u20131052."},{"issue":"3","key":"e_1_3_2_83_2","doi-asserted-by":"crossref","first-page":"84","DOI":"10.3390\/axioms9030084","article-title":"Sequent-type calculi for three-valued and disjunctive default logic","volume":"9","author":"Pkhakadze Sopo","year":"2020","unstructured":"Sopo Pkhakadze and Hans Tompits. 2020. Sequent-type calculi for three-valued and disjunctive default logic. Axioms 9, 3 (2020), 84.","journal-title":"Axioms"},{"key":"e_1_3_2_84_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(80)90014-4"},{"key":"e_1_3_2_85_2","volume-title":"Proceedings of the 16th International Joint Conference on Artificial Intelligence (ICJAI\u201999)","author":"Rosati Riccardo","year":"1999","unstructured":"Riccardo Rosati. 1999. Model checking for nonmonotonic logics: Algorithms and complexity. In Proceedings of the 16th International Joint Conference on Artificial Intelligence (ICJAI\u201999), Thomas Dean (Ed.). The AAAI Press."},{"key":"e_1_3_2_86_2","first-page":"425","volume-title":"Handbook of Satisfiability","author":"Samer Marko","year":"2009","unstructured":"Marko Samer and Stefan Szeider. 2009. Fixed-parameter tractability. In Handbook of Satisfiability, Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh (Eds.). IOS Press, 425\u2013454."},{"key":"e_1_3_2_87_2","first-page":"216","volume-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC\u201978)","author":"Schaefer Thomas J.","year":"1978","unstructured":"Thomas J. Schaefer. 1978. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC\u201978), Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, and Alfred V. Aho (Eds.). Association for Computing Machinery, New York, NY, 216\u2013226. DOI:10.1145\/800133.804350"},{"key":"e_1_3_2_88_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120931"},{"key":"e_1_3_2_89_2","volume-title":"Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI\u201923)","author":"Semenov Alexander","year":"2023","unstructured":"Alexander Semenov, Daniil Chivilikhin, Stepan Kochemazov, and Ibragim Dzhiblavi. 2023. Probabilistic generalization of backdoor trees with application to SAT. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI\u201923). The AAAI Press, Article 456, 9 pages. DOI:10.1609\/aaai.v37i4.25525"},{"key":"e_1_3_2_90_2","first-page":"10353","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201922)","volume":"36","author":"Semenov Alexander","year":"2022","unstructured":"Alexander Semenov, Artem Pavlenko, Daniil Chivilikhin, and Stepan Kochemazov. 2022. On probabilistic generalization of backdoors in boolean satisfiability. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201922), Vasant Honavar and Matthijs Spaan (Eds.), Vol. 36. The AAAI Press, 10353\u201310361. DOI:10.1609\/aaai.v36i9.21277"},{"key":"e_1_3_2_91_2","first-page":"571","volume-title":"Proceedings of the 8th National Conference on Artificial Intelligence (AAAI\u201990)","volume":"1","author":"Stillman Jonathan P.","year":"1990","unstructured":"Jonathan P. Stillman. 1990. It\u2019s not my default: The complexity of membership problems in restricted propositional default logics. In Proceedings of the 8th National Conference on Artificial Intelligence (AAAI\u201990), Thomas Dietterich and William Swartout (Eds.), Vol. 1. The AAAI Press, 571\u2013578."},{"key":"e_1_3_2_92_2","volume-title":"Proceedings of the 8th Canadian Artificial Intelligence Conference (AI\u201990)","author":"Stillman Jonathan P.","year":"1990","unstructured":"Jonathan P. Stillman. 1990. The complexity of horn theories with normal unary defaults. In Proceedings of the 8th Canadian Artificial Intelligence Conference (AI\u201990)."},{"issue":"3","key":"e_1_3_2_93_2","first-page":"205","article-title":"A unifying approach for nonmonotonic S4F, (Reflexive) autoepistemic logic, and answer set programming","volume":"176","author":"Su Ezgi Iraz","year":"2020","unstructured":"Ezgi Iraz Su. 2020. A unifying approach for nonmonotonic S4F, (Reflexive) autoepistemic logic, and answer set programming. Fundam. Inf. 176, 3-4 (2020), 205\u2013234.","journal-title":"Fundam. Inf."},{"key":"e_1_3_2_94_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/978-3-540-24605-3_15","volume-title":"Proceedings of the 6th International Conference Theory and Applications of Satisfiability (SAT\u201903),","volume":"2919","author":"Szeider Stefan","year":"2004","unstructured":"Stefan Szeider. 2004. On fixed-parameter tractable parameterizations of SAT. In Proceedings of the 6th International Conference Theory and Applications of Satisfiability (SAT\u201903),Lecture Notes in Computer Science, Vol. 2919, Enrico Giunchiglia and Armando Tacchella (Eds.). Springer Verlag, 188\u2013202."},{"key":"e_1_3_2_95_2","volume-title":"On the Complexity of Fragments of Nonmonotonic Logics","author":"Thomas Michael","year":"2010","unstructured":"Michael Thomas. 2010. On the Complexity of Fragments of Nonmonotonic Logics. Ph. D. Dissertation. University of Hanover."},{"key":"e_1_3_2_96_2","first-page":"1173","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI\u201903)","author":"Williams Ryan","year":"2003","unstructured":"Ryan Williams, Carla Gomes, and Bart Selman. 2003. Backdoors to typical case complexity. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI\u201903), Georg Gottlob and Toby Walsh (Eds.). Morgan Kaufmann, 1173\u20131178."},{"key":"e_1_3_2_97_2","first-page":"222","volume-title":"Informal Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201903)","author":"Williams Ryan","year":"2003","unstructured":"Ryan Williams, Carla Gomes, and Bart Selman. 2003. On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In Informal Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201903). 222\u2013230."},{"key":"e_1_3_2_98_2","first-page":"626","volume-title":"Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems (AAMAS\u201916)","author":"Young Anthony P.","year":"2016","unstructured":"Anthony P. Young, Sanjay Modgil, and Odinaldo Rodrigues. 2016. Prioritised default logic as rational argumentation. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems (AAMAS\u201916), John Thangarajah, Karl Tuyls, Catholijn M. Jonker, and Stacy C. Marsella (Eds.). Association for Computing Machinery, New York, 626\u2013634."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3655024","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3655024","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:51Z","timestamp":1750291431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3655024"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,17]]},"references-count":97,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3655024"],"URL":"https:\/\/doi.org\/10.1145\/3655024","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2024,6,17]]},"assertion":[{"value":"2023-10-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}