{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:35Z","timestamp":1759637615246,"version":"3.41.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319662626"},{"type":"electronic","value":"9783319662633"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-66263-3_21","type":"book-chapter","created":{"date-parts":[[2017,8,8]],"date-time":"2017-08-08T08:05:11Z","timestamp":1502179511000},"page":"326-343","source":"Crossref","is-referenced-by-count":5,"title":["From DQBF to QBF by Dependency Elimination"],"prefix":"10.1007","author":[{"given":"Ralf","family":"Wimmer","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Karrenbauer","sequence":"additional","affiliation":[]},{"given":"Ruben","family":"Becker","sequence":"additional","affiliation":[]},{"given":"Christoph","family":"Scholl","sequence":"additional","affiliation":[]},{"given":"Bernd","family":"Becker","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,9]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.tcs.2013.12.020","volume":"523","author":"V Balabanov","year":"2014","unstructured":"Balabanov, V., Chiang, H.K., Jiang, J.R.: Henkin quantifiers and Boolean formulae: a certification perspective of DQBF. Theor. Comput. Sci. 523, 86\u2013100 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"21_CR2","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/0095-8956(82)90029-6","volume":"32","author":"LW Beineke","year":"1982","unstructured":"Beineke, L.W., Little, C.H.C.: Cycles in bipartite tournaments. J. Comb. Theor. Ser. B 32(2), 140\u2013145 (1982)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"21_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/978-3-319-40970-2_30","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2016","author":"O Beyersdorff","year":"2016","unstructured":"Beyersdorff, O., Chew, L., Schmidt, R.A., Suda, M.: Lifting QBF resolution calculi to DQBF. In: Creignou, N., Le Berre, D. (eds.) SAT 2016. LNCS, vol. 9710, pp. 490\u2013499. Springer, Cham (2016). doi: 10.1007\/978-3-319-40970-2_30"},{"key":"21_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-54013-4_1","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"R Bloem","year":"2014","unstructured":"Bloem, R., K\u00f6nighofer, R., Seidl, M.: SAT-based synthesis methods for safety specs. In: McMillan, K.L., Rival, X. (eds.) VMCAI 2014. LNCS, vol. 8318, pp. 1\u201320. Springer, Heidelberg (2014). doi: 10.1007\/978-3-642-54013-4_1"},{"key":"21_CR5","unstructured":"Bubeck, U.: Model-based transformations for quantified Boolean formulas. Ph.D. thesis, University of Paderborn (2010)"},{"key":"21_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/11814948_21","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"U Bubeck","year":"2006","unstructured":"Bubeck, U., B\u00fcning, H.K.: Dependency quantified horn formulas: models and complexity. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 198\u2013211. Springer, Heidelberg (2006). doi: 10.1007\/11814948_21"},{"issue":"2","key":"21_CR7","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1287\/moor.27.2.361.328","volume":"27","author":"M Cai","year":"2002","unstructured":"Cai, M., Deng, X., Zang, W.: A min-max theorem on feedback vertex sets. Math. Oper. Res. 27(2), 361\u2013371 (2002)","journal-title":"Math. Oper. Res."},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T.A., Otop, J., Pavlogiannis, A.: Distributed synthesis for LTL fragments. In: FMCAD 2013, pp. 18\u201325. IEEE, October 2013","DOI":"10.1109\/FMCAD.2013.6679386"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-319-09284-3_19","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2014","author":"B Finkbeiner","year":"2014","unstructured":"Finkbeiner, B., Tentrup, L.: Fast DQBF refutation. In: Sinz, C., Egly, U. (eds.) SAT 2014. LNCS, vol. 8561, pp. 243\u2013251. Springer, Cham (2014). doi: 10.1007\/978-3-319-09284-3_19"},{"key":"21_CR10","unstructured":"Fr\u00f6hlich, A., Kov\u00e1sznai, G., Biere, A.: A DPLL algorithm for solving DQBF. In: International Workshop on Pragmatics of SAT (POS), Trento, Italy (2012)"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Fr\u00f6hlich, A., Kov\u00e1sznai, G., Biere, A., Veith, H.: iDQ: instantiation-based DQBF solving. In: Le Berre, D. (ed.) International Workshop on Pragmatics of SAT (POS 2014), Vienna, Austria. EPiC Series, vol. 27, pp. 103\u2013116. EasyChair, July 2014","DOI":"10.29007\/1s5k"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Gitina, K., Reimer, S., Sauer, M., Wimmer, R., Scholl, C., Becker, B.: Equivalence checking of partial designs using dependency quantified Boolean formulae. In: ICCD 2013, Asheville, NC, USA, pp. 396\u2013403. IEEE CS, October 2013","DOI":"10.1109\/ICCD.2013.6657071"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Gitina, K., Wimmer, R., Reimer, S., Sauer, M., Scholl, C., Becker, B.: Solving DQBF through quantifier elimination. In: DATE 2015, Grenoble, France. IEEE, March 2015","DOI":"10.7873\/DATE.2015.0098"},{"issue":"2\u20133","key":"21_CR14","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.ipl.2006.11.016","volume":"102","author":"J Guo","year":"2007","unstructured":"Guo, J., H\u00fcffner, F., Moser, H.: Feedback arc set in bipartite tournaments is NP-complete. Inf. Process. Lett. 102(2\u20133), 62\u201365 (2007)","journal-title":"Inf. Process. Lett."},{"key":"21_CR15","unstructured":"Henkin, L.: Some remarks on infinitely long formulas. In: Infinitistic Methods: Proceedings of the 1959 Symposium on Foundations of Mathematics, Warsaw, pp. 167\u2013183. Panstwowe Wydawnictwo Naukowe, Panstwowe, September 1961"},{"key":"21_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/978-3-642-31612-8_10","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2012","author":"M Janota","year":"2012","unstructured":"Janota, M., Klieber, W., Marques-Silva, J., Clarke, E.: Solving QBF with counterexample guided refinement. In: Cimatti, A., Sebastiani, R. (eds.) SAT 2012. LNCS, vol. 7317, pp. 114\u2013128. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-31612-8_10"},{"key":"21_CR17","unstructured":"Janota, M., Marques-Silva, J.: Solving QBF by clause selection. In: Yang, Q., Wooldridge, M. (eds.) IJCAI 2015, Buenos Aires, Argentina, pp. 325\u2013331. AAAI Press (2015). http:\/\/ijcai.org\/Abstract\/15\/052"},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of the Symposium on the Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York, IBM Thomas J. Watson Research Center, Yorktown Heights (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"2\u20133","key":"21_CR19","first-page":"71","volume":"7","author":"F Lonsing","year":"2010","unstructured":"Lonsing, F., Biere, A.: DepQBF: a dependency-aware QBF solver. J. Satisf. Boolean Model. Comput. 7(2\u20133), 71\u201376 (2010)","journal-title":"J. Satisf. Boolean Model. Comput."},{"key":"21_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-662-44199-2_48","volume-title":"Mathematical Software \u2013 ICMS 2014","author":"F Lonsing","year":"2014","unstructured":"Lonsing, F., Egly, U.: Incremental QBF solving by DepQBF. In: Hong, H., Yap, C. (eds.) ICMS 2014. LNCS, vol. 8592, pp. 307\u2013314. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-44199-2_48"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Stockmeyer, L.J.: Word problems requiring exponential time: preliminary report. In: STOC, pp. 1\u20139. ACM Press (1973)","DOI":"10.1145\/800125.804029"},{"issue":"7\u20138","key":"21_CR22","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1016\/S0898-1221(00)00333-3","volume":"41","author":"G Peterson","year":"2001","unstructured":"Peterson, G., Reif, J., Azhar, S.: Lower bounds for multiplayer non-cooperative games of incomplete information. Comput. Math. Appl. 41(7\u20138), 957\u2013992 (2001)","journal-title":"Comput. Math. Appl."},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Pigorsch, F., Scholl, C.: Exploiting structure in an AIG based QBF solver. In: DATE 2009, Nice, France, pp. 1596\u20131601. IEEE, April 2009","DOI":"10.1109\/DATE.2009.5090919"},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"Pigorsch, F., Scholl, C.: An AIG-based QBF-solver using SAT for preprocessing. In: Sapatnekar, S.S. (ed.) DAC 2010, Anaheim, CA, USA, pp. 170\u2013175. ACM Press, July 2010","DOI":"10.1145\/1837274.1837318"},{"key":"21_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1007\/978-3-540-89439-1_49","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"M Samer","year":"2008","unstructured":"Samer, M.: Variable dependencies of quantified CSPs. In: Cervesato, I., Veith, H., Voronkov, A. (eds.) LPAR 2008. LNCS, vol. 5330, pp. 512\u2013527. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-89439-1_49"},{"issue":"1","key":"21_CR26","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/s10817-008-9114-5","volume":"42","author":"M Samer","year":"2009","unstructured":"Samer, M., Szeider, S.: Backdoor sets of quantified Boolean formulas. J. Autom. Reason. 42(1), 77\u201397 (2009)","journal-title":"J. Autom. Reason."},{"key":"21_CR27","doi-asserted-by":"crossref","unstructured":"Scholl, C., Becker, B.: Checking equivalence for partial implementations. In: DAC 2001, Las Vegas, NV, USA, pp. 238\u2013243. ACM Press, June 2001","DOI":"10.1145\/378239.378471"},{"key":"21_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/978-3-642-31612-8_6","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2012","author":"F Slivovsky","year":"2012","unstructured":"Slivovsky, F., Szeider, S.: Computing resolution-path dependencies in linear time. In: Cimatti, A., Sebastiani, R. (eds.) SAT 2012. LNCS, vol. 7317, pp. 58\u201371. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-31612-8_6"},{"key":"21_CR29","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/s10817-015-9353-1","volume":"56","author":"F Slivovsky","year":"2015","unstructured":"Slivovsky, F., Szeider, S.: Quantifier reordering for QBF. J. Autom. Reason. 56, 459\u2013477 (2015)","journal-title":"J. Autom. Reason."},{"key":"21_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/978-3-642-23786-7_59","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2011","author":"A Gelder","year":"2011","unstructured":"Gelder, A.: Variable independence and resolution paths for quantified Boolean formulas. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 789\u2013803. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-23786-7_59"},{"key":"21_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-319-46520-3_25","volume-title":"Automated Technology for Verification and Analysis","author":"K Wimmer","year":"2016","unstructured":"Wimmer, K., Wimmer, R., Scholl, C., Becker, B.: Skolem functions for DQBF. In: Artho, C., Legay, A., Peled, D. (eds.) ATVA 2016. LNCS, vol. 9938, pp. 395\u2013411. Springer, Cham (2016). doi: 10.1007\/978-3-319-46520-3_25"},{"key":"21_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-319-24318-4_13","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2015","author":"R Wimmer","year":"2015","unstructured":"Wimmer, R., Gitina, K., Nist, J., Scholl, C., Becker, B.: Preprocessing for DQBF. In: Heule, M., Weaver, S. (eds.) SAT 2015. LNCS, vol. 9340, pp. 173\u2013190. Springer, Cham (2015). doi: 10.1007\/978-3-319-24318-4_13"},{"key":"21_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/978-3-662-54577-5_21","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"R Wimmer","year":"2017","unstructured":"Wimmer, R., Reimer, S., Marin, P., Becker, B.: HQSpre \u2013 an effective preprocessor for QBF and DQBF. In: Legay, A., Margaria, T. (eds.) TACAS 2017. LNCS, vol. 10205, pp. 373\u2013390. Springer, Heidelberg (2017). doi: 10.1007\/978-3-662-54577-5_21"},{"key":"21_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/978-3-319-40970-2_29","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2016","author":"R Wimmer","year":"2016","unstructured":"Wimmer, R., Scholl, C., Wimmer, K., Becker, B.: Dependency schemes for DQBF. In: Creignou, N., Le Berre, D. (eds.) SAT 2016. LNCS, vol. 9710, pp. 473\u2013489. Springer, Cham (2016). doi: 10.1007\/978-3-319-40970-2_29"},{"key":"21_CR35","doi-asserted-by":"crossref","unstructured":"Wimmer, R., Wimmer, K., Scholl, C., Becker, B.: Analysis of incomplete circuits using dependency quantified Boolean formulas. In: International Workshop on Logic and Synthesis (IWLS) (2016)","DOI":"10.1007\/978-3-319-67295-3_7"},{"key":"21_CR36","volume-title":"Integer Programming","author":"LA Wolsey","year":"1998","unstructured":"Wolsey, L.A.: Integer Programming. Wiley-Interscience, New York (1998)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2017"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-66263-3_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T20:59:54Z","timestamp":1750798794000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-66263-3_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319662626","9783319662633"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-66263-3_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}