{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T13:21:35Z","timestamp":1754486495213},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56503-5_57","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:16:34Z","timestamp":1330254994000},"page":"576-585","source":"Crossref","is-referenced-by-count":18,"title":["Frontiers of feasible and probabilistic feasible Boolean manipulation with branching programs"],"prefix":"10.1007","author":[{"given":"Jordan","family":"Gergov","sequence":"first","affiliation":[]},{"given":"Christoph","family":"Meinel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"57_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, L. Babai, P. Hajnal, J. Komlos, P. Pudlak, V. R\u00f6dl, E. Szemeredi, G. Turan: Two Lower Bounds for Branching Programs, Proc. 18. ACM STOC, 1986, 30\u201338.","DOI":"10.1145\/12130.12134"},{"key":"57_CR2","doi-asserted-by":"crossref","unstructured":"K. S. Brace, R. E. Bryant, R. L. Rudell: Efficient Implementation of a BDD package. Proc. of 27th Design Automation Conf., 1990, 40\u201345.","DOI":"10.1145\/123186.123222"},{"key":"57_CR3","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0020-0190(80)90078-2","volume":"2","author":"M. Blum","year":"1980","unstructured":"M. Blum, A. K. Chandra, M. N. Wegman: Equivalence of Free Boolean Graphs Can Be Decided Probabilistically in Polynomial Time, IPL 10, 2, 1980, 80\u201382.","journal-title":"IPL 10"},{"key":"57_CR4","unstructured":"Y. Breitbart, H. B. Hunt III, D. Rosenkrantz: The Size of Binary Decision Diagrams Representing Boolean Functions, submitted to Inf. and Comp. 1991."},{"issue":"8","key":"57_CR5","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"C-35","author":"R. E. Bryant","year":"1986","unstructured":"R. E. Bryant: Graph-Based Algorithms for Boolean Function Manipulation, IEEE Trans. Computers, C-35, 8, 1986, 677\u2013691.","journal-title":"IEEE Trans. Computers"},{"key":"57_CR6","doi-asserted-by":"crossref","unstructured":"R. E. Bryant: Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams, to appear in IEEE Trans. Computers, 1992.","DOI":"10.1145\/136035.136043"},{"key":"57_CR7","doi-asserted-by":"crossref","unstructured":"J. R. Burch, E. M. Clarke, K. L. McMillan, D.L. Dill: Sequential Circuit Verification Using Symbolic Model Checking, Proc. 27th IEEE DAC'90, 1990, 46\u201351.","DOI":"10.1145\/123186.123223"},{"key":"57_CR8","unstructured":"R. L. Constable, H. B. Hunt III, S. Salmi: On the Computational Complexity of Scheme Equivalence, Proc. 8th Princeton Conf. on Information Sciences and Systems, 1974."},{"key":"57_CR9","first-page":"227","volume":"62","author":"S. Fortune","year":"1978","unstructured":"S. Fortune, J. Hopcroft, E. M. Schmidt: The Complexity of Equivalence and Containment for Free Single Program Schemes. LNCS 62, 1978, 227\u2013240.","journal-title":"LNCS"},{"key":"57_CR10","unstructured":"M. Fuita, H. Fujisawa, N. Kawoto: Evaluation and Improvements of Boolean Comparison Method Based on Binary Decision Diagrams, Proc. IEEE ICCAD'88, 1988, 2\u20135."},{"key":"57_CR11","doi-asserted-by":"crossref","unstructured":"J. Gergov, Ch. Meinel: Analysis and Manipulation of Boolean Functions in Terms of Decision Graphs, Proc. WG'92, LNCS, 1992.","DOI":"10.1007\/3-540-56402-0_56"},{"key":"57_CR12","unstructured":"J. Gergov, Ch. Meinel: Efficient Analysis and Manipulation of OBDDs Can Be Extended to Read-once-only Branching Programs, Forschungsbericht Nr. 92-10, Univ. Trier, 1992."},{"key":"57_CR13","unstructured":"R. Lidl, H. Niederreiter: Introduction to Finite Fields and Their Applications. Cambridge University Press, 1986."},{"key":"57_CR14","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0304-3975(91)90021-S","volume":"86","author":"M. Krause","year":"1991","unstructured":"M. Krause, Ch. Meinel, S. Waack: Separating the Eraser Turing Machine Classes L e , N Le, co-N Le and P e , TCS 86 (1991), 267\u2013275.","journal-title":"TCS"},{"key":"57_CR15","doi-asserted-by":"crossref","unstructured":"Ch. Meinel: The Power of Polynomial Size \u03a9-Branching Programs, Proc. STACS'88 (Bourdeaux), LNCS 294, 81\u201390.","DOI":"10.1007\/BFb0035834"},{"key":"57_CR16","unstructured":"Ch. Meinel: Modified Branching Programs and Their Computational Power, Springer-Verlag, LNCS 370, 1989."},{"key":"57_CR17","unstructured":"Ch. Meinel: Branching Programs-An Efficient Data Structure for Computer-Aided Circuit Design, Preprint UGH Paderborn, Nr. 93, 1991."},{"key":"57_CR18","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1109\/12.35836","volume":"C-38","author":"S. Muroga","year":"1989","unstructured":"S. Muroga, Y. Kambayashi, H. C. Lai, J. N. Culliney: The Transduction Method, IEEE Trans. Computers, C-38, 1989, 1404\u20131424.","journal-title":"IEEE Trans. Computers"},{"key":"57_CR19","unstructured":"S. Malik, A. Wang, It. Bryant, A. Sangiovanni-Vincentelli: Logical Verification Using Binary Decision Diagrams in a Logical Synthesis Environment. Proc. IEEE Intern. Conf. on CAD, 1988, 6\u20139."},{"key":"57_CR20","unstructured":"D. Sieling, I. Wegener: Graph Driven BDDs \u2014 A New Data Structure for Boolean Functions, personal communications, manuscript."}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_57.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:04:28Z","timestamp":1605647068000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}