{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T09:32:36Z","timestamp":1742635956304,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_40","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:44Z","timestamp":1330290284000},"page":"491-502","source":"Crossref","is-referenced-by-count":7,"title":["Read-once projections and formal circuit verification with binary decision diagrams"],"prefix":"10.1007","author":[{"given":"Beate","family":"Bollig","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ingo","family":"Wegener","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"M. Ajtai, L. Babai, A. Hajnal, J. Koml\u00f3s, P. Pudl\u00e1k, V. R\u00f6dl, E. Szemer\u00e9di and G. Tur\u00e1n: Two lower bounds for branching programs. 18. STOC, 30\u201338 (1986).","key":"40_CR1","DOI":"10.1145\/12130.12134"},{"key":"40_CR2","first-page":"71","volume":"911","author":"B. Becker","year":"1995","unstructured":"B. Becker, R. Drechsler and R. Werchner: On the relation between BDDs and FDDs. LATIN '95, LNCS 911, 71\u201383 (1995).","journal-title":"LATIN '95, LNCS"},{"unstructured":"B. Bollig, M. Sauerhoff, D. Sieling and I. Wegener: On the power of different types of restricted branching programs. Submitted to Theoretical Computer Science. Electronic Colloquium in Computational Complexity, TR 94-026 (1994).","key":"40_CR3"},{"doi-asserted-by":"crossref","unstructured":"B. Bollig and I. Wegener: Read-once projections and formal circuit verification with binary decision diagrams. Electronic Colloquium in Computational Complexity, TR 95-045 (1995).","key":"40_CR4","DOI":"10.1007\/3-540-60922-9_40"},{"key":"40_CR5","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"R. E. Bryant","year":"1986","unstructured":"R. E. Bryant: Graph-based algorithms for Boolean function manipulation. IEEE Trans. on Computers 35, 677\u2013691 (1986).","journal-title":"IEEE Trans. on Computers"},{"key":"40_CR6","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1145\/136035.136043","volume":"24","author":"R. E. Bryant","year":"1992","unstructured":"R. E. Bryant: Symbolic Boolean manipulation with ordered binary decision diagrams. ACM Computing Surveys 24, 293\u2013318 (1992).","journal-title":"ACM Computing Surveys"},{"key":"40_CR7","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. Chandra","year":"1984","unstructured":"A. Chandra, L. Stockmeyer and U. Vishkin: Constant depth reducibility. SIAM J. on Computing 13, 423\u2013439 (1984).","journal-title":"SIAM J. on Computing"},{"key":"40_CR8","volume-title":"Computers and intractability \u2014 a guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. B. Johnson: Computers and intractability \u2014 a guide to the theory of NP-completeness. Freeman, New York 1979."},{"key":"40_CR9","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1109\/12.324545","volume":"43","author":"J. Gergov","year":"1994","unstructured":"J. Gergov and C. Meinel: Efficient Boolean manipulation with OBDDs can be extended to FBDDs. IEEE Trans. on Computers 43, 1197\u20131209 (1994).","journal-title":"IEEE Trans. on Computers"},{"doi-asserted-by":"crossref","unstructured":"A. Hajnal, W. Maass, P. Pudl\u00e1k, M. Szegedy and G. Tur\u00e1n: Threshold circuits of bounded depth. 28. FOCS, 99\u2013110 (1987).","key":"40_CR10","DOI":"10.1109\/SFCS.1987.59"},{"doi-asserted-by":"crossref","unstructured":"J. Jain, M. Abadir, J. Bitner, D. S. Fussell and J. A. Abraham: IBDDs: an efficient functional representation for digital circuits. Proc. European Design Automation Conf., 440\u2013446 (1992).","key":"40_CR11","DOI":"10.1109\/EDAC.1992.205973"},{"doi-asserted-by":"crossref","unstructured":"U. Kebschull, E. Schubert and W. Rosenstiel: Multilevel logic synthesis based on functional decision diagrams. Proc. European Design Automation Conf., 43\u201347 (1992).","key":"40_CR12","DOI":"10.1109\/EDAC.1992.205890"},{"key":"40_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(91)90072-A","volume":"91","author":"M. Krause","year":"1991","unstructured":"M. Krause: Lower bounds for depth-restricted branching programs. Information and Computation 91, 1\u201314 (1991).","journal-title":"Information and Computation"},{"key":"40_CR14","first-page":"405","volume":"324","author":"M. Krause","year":"1988","unstructured":"M. Krause, C. Meinel and S. Waack: Separating the eraser Turing machine classes L e , NL e , coNL e and P e. MFCS, LNCS 324, 405\u2013413 (1988).","journal-title":"MFCS, LNCS"},{"key":"40_CR15","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/0222016","volume":"22","author":"N. Nisan","year":"1993","unstructured":"N. Nisan and A. Wigderson: Rounds in communication complexity revisited. SIAM J. on Computing 22, 211\u2013219 (1993).","journal-title":"SIAM J. on Computing"},{"doi-asserted-by":"crossref","unstructured":"S. Ponzio: A lower bound for integer multiplication with read-once branching programs. 27. STOC, 130\u2013139 (1995) (see also Ph. D. Thesis, MIT\/LCS-TR-633. Sept. 1995).","key":"40_CR16","DOI":"10.1145\/225058.225098"},{"key":"40_CR17","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/0304-3975(94)00078-W","volume":"141","author":"D. Sieling","year":"1995","unstructured":"D. Sieling and I. Wegener: Graph driven BDDs \u2014 a new data structure for Boolean functions. Theoretical Computer Science 141, 283\u2013310 (1995).","journal-title":"Theoretical Computer Science"},{"key":"40_CR18","doi-asserted-by":"publisher","first-page":"946","DOI":"10.1109\/18.256501","volume":"39","author":"K. S. Siu","year":"1993","unstructured":"K. S. Siu, J. Bruck, T. Kailath and T. Hofmeister: Depth-efficient neural networks for division and related problems. IEEE Trans. on Information Theory 39, 946\u2013956 (1993).","journal-title":"IEEE Trans. on Information Theory"},{"key":"40_CR19","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1145\/3149.3158","volume":"32","author":"S. Skyum","year":"1985","unstructured":"S. Skyum and L. G. Valiant: A complexity theory based on Boolean algebra. Journal of the ACM 32, 484\u2013502 (1985).","journal-title":"Journal of the ACM"},{"key":"40_CR20","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0020-0190(93)90202-K","volume":"46","author":"I. Wegener","year":"1993","unstructured":"I. Wegener: Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions. Information Processing Letters 46, 85\u201387 (1993).","journal-title":"Information Processing Letters"},{"key":"40_CR21","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0012-365X(95)90790-R","volume":"136","author":"I. Wegener","year":"1994","unstructured":"I. Wegener: Efficient data structures for Boolean functions. Discrete Mathematics 136, 347\u2013372 (1994).","journal-title":"Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:52Z","timestamp":1742598652000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}