{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,13]],"date-time":"2026-11-13T11:14:09Z","timestamp":1794568449727,"version":"4.9.1"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319941431","type":"print"},{"value":"9783319941448","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94144-8_15","type":"book-chapter","created":{"date-parts":[[2018,6,25]],"date-time":"2018-06-25T04:36:02Z","timestamp":1529901362000},"page":"235-252","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["QBF as an Alternative to Courcelle\u2019s Theorem"],"prefix":"10.1007","author":[{"given":"Michael","family":"Lampis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Mengel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valia","family":"Mitsou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,6,26]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Arieli, O., Caminada, M.W.A.: A general QBF-based formalization of abstract argumentation theory. In: Verheij, B., Szeider, S., Woltran, S. (eds.) Computational Models of Argument, COMMA 2012, pp. 105\u2013116 (2012)","DOI":"10.3233\/978-1-61499-111-3-105"},{"issue":"1","key":"15_CR2","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Appl. Math. 23(1), 11\u201324 (1989)","journal-title":"Discrete Appl. Math."},{"issue":"7","key":"15_CR3","doi-asserted-by":"publisher","first-page":"1415","DOI":"10.1016\/j.jcss.2014.04.014","volume":"80","author":"A Atserias","year":"2014","unstructured":"Atserias, A., Oliva, S.: Bounded-width QBF is PSPACE-complete. J. Comput. Syst. Sci. 80(7), 1415\u20131429 (2014)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"15_CR4","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: An o(c$${}^{\\wedge }$$k\u00a0n) 5-approximation algorithm for treewidth. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, pp. 499\u2013508 (2013)","DOI":"10.1109\/FOCS.2013.60"},{"issue":"2","key":"15_CR6","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0022-0000(05)80004-2","volume":"48","author":"M Cadoli","year":"1994","unstructured":"Cadoli, M., Lenzerini, M.: The complexity of propositional closed world reasoning and circumscription. J. Comput. Syst. Sci. 48(2), 255\u2013310 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR7","unstructured":"Chen, H.: Quantified constraint satisfaction and bounded treewidth. In: de M\u00e1ntaras, R.L., Saitta, L. (eds.) Proceedings of the 16th European Conference on Artificial Intelligence, ECAI 2004, pp. 161\u2013165 (2004)"},{"issue":"1","key":"15_CR8","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"15_CR9","unstructured":"DIMACS: Satisfiability: Suggested Format. DIMACS Challenge. DIMACS (1993)"},{"issue":"2","key":"15_CR10","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0004-3702(94)00041-X","volume":"77","author":"PM Dung","year":"1995","unstructured":"Dung, P.M.: On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77(2), 321\u2013358 (1995)","journal-title":"Artif. Intell."},{"issue":"10\u201315","key":"15_CR11","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1016\/j.artint.2007.03.006","volume":"171","author":"PE Dunne","year":"2007","unstructured":"Dunne, P.E.: Computational properties of argument systems satisfying graph-theoretic constraints. Artif. Intell. 171(10\u201315), 701\u2013729 (2007)","journal-title":"Artif. Intell."},{"issue":"1\/2","key":"15_CR12","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/S0004-3702(02)00261-8","volume":"141","author":"PE Dunne","year":"2002","unstructured":"Dunne, P.E., Bench-Capon, T.J.M.: Coherence in finite argument systems. Artif. Intell. 141(1\/2), 187\u2013203 (2002)","journal-title":"Artif. Intell."},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2012.03.005","volume":"186","author":"W Dvor\u00e1k","year":"2012","unstructured":"Dvor\u00e1k, W., Pichler, R., Woltran, S.: Towards fixed-parameter tractable algorithms for abstract argumentation. Artif. Intell. 186, 1\u201337 (2012)","journal-title":"Artif. Intell."},{"key":"15_CR14","unstructured":"Egly, U., Woltran, S.: Reasoning in argumentation frameworks using quantified boolean formulas. In: Dunne, P.E., Bench-Capon, T.J.M. (eds.) Computational Models of Argument, COMMA 2006, pp. 133\u2013144 (2006)"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Eiben, E., Ganian, R., Ordyniak, S.: Using decomposition-parameters for QBF: mind the prefix! In: Schuurmans, D., Wellman, M.P. (eds.) Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pp. 964\u2013970 (2016)","DOI":"10.1609\/aaai.v30i1.10113"},{"key":"15_CR16","unstructured":"Eiben, E., Ganian, R., Ordyniak, S.: Small resolution proofs for QBF using dependency treewidth. CoRR, abs\/1711.02120 (2017)"},{"issue":"2","key":"15_CR17","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0304-3975(93)90073-3","volume":"114","author":"T Eiter","year":"1993","unstructured":"Eiter, T., Gottlob, G.: Propositional circumscription and extended closed-world reasoning are $$\\varPi ^{p}_2$$-complete. Theor. Comput. Sci. 114(2), 231\u2013245 (1993)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"15_CR18","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/200836.200838","volume":"42","author":"T Eiter","year":"1995","unstructured":"Eiter, T., Gottlob, G.: The complexity of logic-based abduction. J. ACM 42(1), 3\u201342 (1995)","journal-title":"J. ACM"},{"issue":"4","key":"15_CR19","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.dam.2006.06.020","volume":"156","author":"E Fischer","year":"2008","unstructured":"Fischer, E., Makowsky, J.A., Ravve, E.V.: Counting truth assignments of formulas of bounded tree-width or clique-width. Discrete Appl. Math. 156(4), 511\u2013529 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"15_CR20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.apal.2004.01.007","volume":"130","author":"M Frick","year":"2004","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130(1\u20133), 3\u201331 (2004)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"1","key":"15_CR21","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.artint.2009.10.003","volume":"174","author":"G Gottlob","year":"2010","unstructured":"Gottlob, G., Pichler, R., Wei, F.: Bounded treewidth as a key to tractability of knowledge representation and reasoning. Artif. Intell. 174(1), 105\u2013132 (2010)","journal-title":"Artif. Intell."},{"key":"15_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-319-23219-5_13","volume-title":"Principles and Practice of Constraint Programming","author":"A Ignatiev","year":"2015","unstructured":"Ignatiev, A., Previti, A., Liffiton, M., Marques-Silva, J.: Smallest MUS extraction with minimal hitting set dualization. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 173\u2013182. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-23219-5_13"},{"key":"15_CR23","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/978-3-540-89439-1_31","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"M Jakl","year":"2008","unstructured":"Jakl, M., Pichler, R., R\u00fcmmele, S., Woltran, S.: Fast counting with bounded treewidth. In: Cervesato, I., Veith, H., Voronkov, A. (eds.) LPAR 2008. LNCS (LNAI), vol. 5330, pp. 436\u2013450. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-89439-1_31"},{"key":"15_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/978-3-642-23786-7_32","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2011","author":"M Janota","year":"2011","unstructured":"Janota, M., Marques-Silva, J.: On deciding MUS membership with QBF. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 414\u2013428. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-23786-7_32"},{"key":"15_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","year":"1994","unstructured":"Kloks, T. (ed.): Treewidth: Computations and Approximations. LNCS, vol. 842. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/BFb0045375"},{"key":"15_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-642-39071-5_21","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2013","author":"J-M Lagniez","year":"2013","unstructured":"Lagniez, J.-M., Biere, A.: Factoring out assumptions to speed up MUS extraction. In: J\u00e4rvisalo, M., Van Gelder, A. (eds.) SAT 2013. LNCS, vol. 7962, pp. 276\u2013292. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39071-5_21"},{"key":"15_CR27","doi-asserted-by":"crossref","unstructured":"Lagniez, J.-M., Lonca, E., Mailly, J.-G.: CoQuiAAS: a constraint-based quick abstract argumentation solver. In: 27th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2015, pp. 928\u2013935 (2015)","DOI":"10.1109\/ICTAI.2015.134"},{"key":"15_CR28","unstructured":"Lampis, M., Mitsou, V.: Treewidth with a quantifier alternation revisited (2017)"},{"key":"15_CR29","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.cosrev.2014.08.001","volume":"13\u201314","author":"A Langer","year":"2014","unstructured":"Langer, A., Reidl, F., Rossmanith, P., Sikdar, S.: Practical algorithms for MSO model-checking on tree-decomposable graphs. Comput. Sci. Rev. 13\u201314, 39\u201374 (2014)","journal-title":"Comput. Sci. Rev."},{"issue":"2","key":"15_CR30","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/j.artint.2004.11.002","volume":"163","author":"P Liberatore","year":"2005","unstructured":"Liberatore, P.: Redundancy in logic I: CNF propositional formulae. Artif. Intell. 163(2), 203\u2013232 (2005)","journal-title":"Artif. Intell."},{"key":"15_CR31","doi-asserted-by":"crossref","unstructured":"Lifschitz, V.: Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 3. Chapter Circumscription, pp. 297\u2013352. Oxford University Press Inc., New York (1994)","DOI":"10.1093\/oso\/9780198537472.003.0006"},{"key":"15_CR32","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"key":"15_CR33","unstructured":"Marx, D., Mitsou, V.: Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pp. 28:1\u201328:15 (2016)"},{"issue":"1","key":"15_CR34","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0004-3702(86)90032-9","volume":"28","author":"J McCarthy","year":"1986","unstructured":"McCarthy, J.: Applications of circumscription to formalizing common-sense knowledge. Artif. Intell. 28(1), 89\u2013116 (1986)","journal-title":"Artif. Intell."},{"key":"15_CR35","unstructured":"Pan, G., Vardi, M.Y.: Fixed-parameter hierarchies inside PSPACE. In: 21st IEEE Symposium on Logic in Computer Science, LICS 2006, pp. 27\u201336 (2006)"},{"issue":"1","key":"15_CR36","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.jda.2009.06.002","volume":"8","author":"M Samer","year":"2010","unstructured":"Samer, M., Szeider, S.: Algorithms for propositional model counting. J. Discrete Algorithms 8(1), 50\u201364 (2010)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"15_CR37","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/582475.582484","volume":"33","author":"M Schaefer","year":"2002","unstructured":"Schaefer, M., Umans, C.: Completeness in the polynomial-time hierarchy: a compendium. SIGACT News 33(3), 32\u201349 (2002)","journal-title":"SIGACT News"},{"key":"15_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-642-21581-0_14","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2011","author":"J Marques-Silva","year":"2011","unstructured":"Marques-Silva, J., Lynce, I.: On improving MUS extraction algorithms. In: Sakallah, K.A., Simon, L. (eds.) SAT 2011. LNCS, vol. 6695, pp. 159\u2013173. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21581-0_14"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2018"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94144-8_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T04:45:38Z","timestamp":1751690738000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-94144-8_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319941431","9783319941448"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94144-8_15","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-319-94144-8","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"26 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Theory and Applications of Satisfiability Testing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Oxford","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 July 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 July 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sat2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/sat2018.azurewebsites.net\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"58","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"34% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2 tool papers were accepted","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}