{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T19:45:24Z","timestamp":1794339924547,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540341666","type":"print"},{"value":"9783540341680","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11753728_60","type":"book-chapter","created":{"date-parts":[[2006,4,27]],"date-time":"2006-04-27T16:17:13Z","timestamp":1146154633000},"page":"600-611","source":"Crossref","is-referenced-by-count":36,"title":["Extended Resolution Proofs for Conjoining BDDs"],"prefix":"10.1007","author":[{"given":"Carsten","family":"Sinz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Armin","family":"Biere","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"60_CR1","doi-asserted-by":"crossref","unstructured":"Davis, M., Putnam, H.: A computing procedure for quantification theory. JACM\u00a07 (1960)","DOI":"10.1145\/321033.321034"},{"key":"60_CR2","doi-asserted-by":"crossref","unstructured":"Davis, M., Logemann, G., Loveland, D.: A machine program for theorem-proving. Communications of the ACM\u00a05(7) (1962)","DOI":"10.1145\/368273.368557"},{"key":"60_CR3","unstructured":"Marques-Silva, J.P., Sakallah, K.A.: GRASP \u2014 a new search algorithm for satisfiability. In: Proc.\u00a0ICCAD 1996 (1996)"},{"key":"60_CR4","doi-asserted-by":"crossref","unstructured":"Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., Malik, S.: Chaff: Engineering an efficient SAT solver. In: Proc.\u00a0DAC 2001 (2001)","DOI":"10.1145\/378239.379017"},{"key":"60_CR5","doi-asserted-by":"crossref","unstructured":"Goldberg, E., Novikov, Y.: BerkMin: A fast and robust SAT-solver. In: Proc.\u00a0DATE 2002 (2002)","DOI":"10.1109\/DATE.2002.998262"},{"key":"60_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-540-24605-3_37","volume-title":"Theory and Applications of Satisfiability Testing","author":"N. E\u00e9n","year":"2004","unstructured":"E\u00e9n, N., S\u00f6rensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 502\u2013518. Springer, Heidelberg (2004)"},{"key":"60_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/3-540-49059-0_14","volume-title":"Tools and Algorithms for the Construction of Analysis of Systems","author":"A. Biere","year":"1999","unstructured":"Biere, A., Cimatti, A., Clarke, E., Zhu, Y.: Symbolic model checking without bDDs. In: Cleaveland, W.R. (ed.) TACAS 1999. LNCS, vol.\u00a01579, pp. 193\u2013207. Springer, Heidelberg (1999)"},{"key":"60_CR8","doi-asserted-by":"crossref","unstructured":"Velev, M., Bryant, R.: Effective use of boolean satisfiability procedures in the formal verification of superscalar and VLIW microprocessors. J.\u00a0Symb.\u00a0Comput.\u00a035(2) (2003)","DOI":"10.1016\/S0747-7171(02)00091-3"},{"key":"60_CR9","doi-asserted-by":"crossref","unstructured":"Shlyakhter, I., Seater, R., Jackson, D., Sridharan, M., Taghdiri, M.: Debugging overconstrained declarative models using unsatisfiable cores. In: Proc.\u00a0ASE 2003 (2003)","DOI":"10.1109\/ASE.2003.1240298"},{"key":"60_CR10","doi-asserted-by":"crossref","unstructured":"Sinz, C., Kaiser, A., K\u00fcchlin, W.: Formal methods for the validation of automotive product configuration data. AI EDAM\u00a017(1) (2003)","DOI":"10.1017\/S0890060403171065"},{"key":"60_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/3-540-36577-X_2","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"K.L. McMillan","year":"2003","unstructured":"McMillan, K.L., Amla, N.: Automatic abstraction without counterexamples. In: Garavel, H., Hatcliff, J. (eds.) TACAS 2003. LNCS, vol.\u00a02619, pp. 2\u201317. Springer, Heidelberg (2003)"},{"key":"60_CR12","doi-asserted-by":"crossref","unstructured":"Xie, Y., Aiken, A.: Scalable error detection using boolean satisfiability. In: Proc.\u00a0POPL 2005 (2005)","DOI":"10.1145\/1040305.1040334"},{"key":"60_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-45069-6_1","volume-title":"Computer Aided Verification","author":"K.L. McMillan","year":"2003","unstructured":"McMillan, K.L.: Interpolation and SAT-based model checking. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol.\u00a02725, pp. 1\u201313. Springer, Heidelberg (2003)"},{"key":"60_CR14","unstructured":"Zhang, L., Malik, S.: Validating SAT solvers using an independent resolution-based checker: Practical implementations and other applications. In: Proc.\u00a0DATE 2003 (2003)"},{"key":"60_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/3-540-45643-0_3","volume-title":"Algorithm Engineering and Experiments","author":"D.B. Motter","year":"2002","unstructured":"Motter, D.B., Markov, I.L.: A compressed breadth-first search for satisfiability. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol.\u00a02409, p. 29. Springer, Heidelberg (2002)"},{"key":"60_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/978-3-540-24605-3_30","volume-title":"Theory and Applications of Satisfiability Testing","author":"J. Franco","year":"2004","unstructured":"Franco, J., Kouril, M., Schlipf, J., Ward, J., Weaver, S., Dransfield, M.R., Vanfleet, W.M.: SBSAT: a state-based, BDD-based satisfiability solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 398\u2013410. Springer, Heidelberg (2004)"},{"key":"60_CR17","doi-asserted-by":"crossref","unstructured":"Damiano, R., Kukula, J.: Checking satisfiability of a conjunction of BDDs. In: DAC 2003 (2003)","DOI":"10.1145\/775832.776039"},{"key":"60_CR18","doi-asserted-by":"crossref","unstructured":"Huang, J., Darwiche, A.: Toward good elimination orders for symbolic SAT solving. In: Proc.\u00a0ICTAI 2004 (2004)","DOI":"10.1109\/ICTAI.2004.115"},{"key":"60_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/11527695_19","volume-title":"Theory and Applications of Satisfiability Testing","author":"G. Pan","year":"2005","unstructured":"Pan, G., Vardi, M.Y.: Search vs. Symbolic techniques in satisfiability solving. In: Hoos, H.H., Mitchell, D.G. (eds.) SAT 2004. LNCS, vol.\u00a03542, pp. 235\u2013250. Springer, Heidelberg (2005)"},{"key":"60_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/11527695_17","volume-title":"Theory and Applications of Satisfiability Testing","author":"H. Jin","year":"2005","unstructured":"Jin, H., Somenzi, F.: CirCUs: A hybrid satisfiability solver. In: Hoos, H.H., Mitchell, D.G. (eds.) SAT 2004. LNCS, vol.\u00a03542, pp. 211\u2013223. Springer, Heidelberg (2005)"},{"key":"60_CR21","doi-asserted-by":"crossref","unstructured":"Bryant, R.: Graph-based algorithms for Boolean function manipulation. IEEE Trans.\u00a0on Comp.\u00a035(8) (1986)","DOI":"10.1109\/TC.1986.1676819"},{"key":"60_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0016843","volume-title":"Constraints in Computational Logics","author":"T.E. Uribe","year":"1994","unstructured":"Uribe, T.E., Stickel, M.E.: Ordered binary decision diagrams and the Davis-Putnam procedure. In: Jouannaud, J.-P. (ed.) CCL 1994. LNCS, vol.\u00a0845, Springer, Heidelberg (1994)"},{"key":"60_CR23","doi-asserted-by":"crossref","unstructured":"Groote, J.F., Zantema, H.: Resolution and binary decision diagrams cannot simulate each other polynomially. Discrete Applied Mathematics\u00a0130(2) (2003)","DOI":"10.1016\/S0166-218X(02)00403-1"},{"key":"60_CR24","unstructured":"Urquhart, A.: The complexity of propositional proofs. Bulletin of the EATCS\u00a064 (1998)"},{"key":"60_CR25","doi-asserted-by":"crossref","unstructured":"Robinson, J.A.: A machine-oriented logic based on the resolution principle. JACM\u00a012 (1965)","DOI":"10.1145\/321250.321253"},{"key":"60_CR26","doi-asserted-by":"crossref","unstructured":"Tseitin, G.: On the complexity of derivation in propositional calculus. In: Studies in Constructive Mathematics and Mathematical Logic (1970)","DOI":"10.1007\/978-1-4899-5327-8_25"},{"key":"60_CR27","doi-asserted-by":"crossref","unstructured":"Cook, S.: A short proof of the pigeon hole principle using extended resolution. SIGACT News\u00a08(4) (1976)","DOI":"10.1145\/1008335.1008338"},{"key":"60_CR28","doi-asserted-by":"crossref","unstructured":"Haken, A.: The intractability of resolution. Theoretical Comp.\u00a0Science 39 (1985)","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"60_CR29","doi-asserted-by":"crossref","unstructured":"Beame, P., Kautz, H., Sabharwal, A.: Towards understanding and harnessing the potential of clause learning. J.\u00a0Artif.\u00a0Intell.\u00a0Res.\u00a0(JAIR)\u00a022 (2004)","DOI":"10.1613\/jair.1410"},{"key":"60_CR30","doi-asserted-by":"crossref","unstructured":"Aloul, F., Ramani, A., Markov, I., Sakallah, K.: Solving difficult instances of boolean satisfiability in the presence of symmetry. IEEE Trans.\u00a0on Comp.\u00a0Aided Design\u00a022(9) (2003)","DOI":"10.1109\/TCAD.2003.816218"},{"key":"60_CR31","doi-asserted-by":"crossref","unstructured":"Plaisted, D., Biere, A., Zhu, Y.: A satisfiability procedure for quantified boolean formulae. Discrete Applied Mathematics\u00a0130(2) (2003)","DOI":"10.1016\/S0166-218X(02)00409-2"},{"key":"60_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/11499107_5","volume-title":"Theory and Applications of Satisfiability Testing","author":"N. E\u00e9n","year":"2005","unstructured":"E\u00e9n, N., Biere, A.: Effective preprocessing in SAT through variable and clause elimination. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol.\u00a03569, pp. 61\u201375. Springer, Heidelberg (2005)"},{"key":"60_CR33","doi-asserted-by":"crossref","unstructured":"Aloul, F., Markov, I., Sakallah, K.: FORCE: A fast and easy\u2013to\u2013implement variable-ordering heuristic. In: ACM Great Lakes Symp.\u00a0on VLSI (2003)","DOI":"10.1145\/764808.764839"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11753728_60.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:03:52Z","timestamp":1619492632000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11753728_60"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540341666","9783540341680"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/11753728_60","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/11753728","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}