{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T04:28:03Z","timestamp":1777868883695,"version":"3.51.4"},"reference-count":39,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1995,7,1]],"date-time":"1995-07-01T00:00:00Z","timestamp":804556800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1995,7,1]],"date-time":"1995-07-01T00:00:00Z","timestamp":804556800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6591,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IRI-9221947"],"award-info":[{"award-number":["IRI-9221947"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR 90-06396"],"award-info":[{"award-number":["CCR 90-06396"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR 89-03319"],"award-info":[{"award-number":["CCR 89-03319"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1995,7]]},"DOI":"10.1016\/0304-3975(94)00181-h","type":"journal-article","created":{"date-parts":[[2003,4,25]],"date-time":"2003-04-25T06:09:04Z","timestamp":1051250944000},"page":"45-69","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":34,"title":["On the size of binary decision diagrams representing Boolean functions"],"prefix":"10.1016","volume":"145","author":[{"given":"Y.","family":"Breitbart","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"III","given":"H.","family":"Hunt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Rosenkrantz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(94)00181-H_BIB1","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1109\/TC.1986.1676774","article-title":"Functional test generation for digital circuits using binary decision diagrams","volume":"C-35","author":"Abadir","year":"1986","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0304-3975(94)00181-H_BIB2","doi-asserted-by":"crossref","first-page":"1461","DOI":"10.1109\/12.8719","article-title":"Binary decision tree test functions","volume":"C-37","author":"Aborhey","year":"1988","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0304-3975(94)00181-H_BIB3","series-title":"Proc. 18th Ann. ACM Symp. on Theory of Computing","first-page":"30","article-title":"Two lower bounds for branching programs","author":"Ajtai","year":"1986"},{"key":"10.1016\/0304-3975(94)00181-H_BIB4","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1109\/TC.1978.1675141","article-title":"Binary decision diagrams","volume":"C-27","author":"Akers","year":"1978","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0304-3975(94)00181-H_BIB5","series-title":"Proc. 8th Ann. Internat. Conf. on Fault-Tolerant Computing","first-page":"75","article-title":"Functional testing with binary decision diagrams","author":"Akers","year":"1978"},{"key":"10.1016\/0304-3975(94)00181-H_BIB6","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0022-0000(87)90010-9","article-title":"A lower bound for read-once-only branching programs","volume":"35","author":"Babai","year":"1987","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(94)00181-H_BIB7","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1137\/0215040","article-title":"Bounds for width two branching programs","volume":"15","author":"Borodin","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(94)00181-H_BIB8_1","unstructured":"Y. Breitbart, Comparison of complexities of realization of Boolean functions by automata and Turing machines. Dokl. Acad. Nauk SSSR 180 (5)."},{"key":"10.1016\/0304-3975(94)00181-H_BIB8_2","author":"Breitbart","year":"1968","journal-title":"Sovjet Physics Dokl. 13"},{"key":"10.1016\/0304-3975(94)00181-H_BIB9","article-title":"Complexity of the calculation of predicates by finite automata","author":"Breitbart","year":"1973","journal-title":"Doctoral Thesis Technion"},{"issue":"3","key":"10.1016\/0304-3975(94)00181-H_BIB10","doi-asserted-by":"crossref","DOI":"10.1016\/S0022-0000(76)80005-0","article-title":"Some bounds on the complexity of predicate recognition by finite automata","volume":"12","author":"Breitbart","year":"1976","journal-title":"J. Comput. System Sci"},{"key":"10.1016\/0304-3975(94)00181-H_BIB11","series-title":"Proc. 16th Allerton Conf. on Communication, Control and Computing","article-title":"A family of Boolean functions with nonlinear formula size","author":"Breitbart","year":"1978"},{"key":"10.1016\/0304-3975(94)00181-H_BIB12","series-title":"Proc. 22nd ACM\/IEEE Design Automation Conf.","first-page":"688","article-title":"Symbolic manipulation of Boolean functions using a graphical representation","author":"Bryant","year":"1985"},{"key":"10.1016\/0304-3975(94)00181-H_BIB13","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","article-title":"Graph-based algorithms for Boolean function manipulation","volume":"C-35","author":"Bryant","year":"1986","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0304-3975(94)00181-H_BIB14","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1109\/TCAD.1985.1270168","article-title":"Simulation of MOS circuits by decision diagrams","volume":"CAD-4","author":"Cerny","year":"1985","journal-title":"IEEE Trans. Comput. Aided Design"},{"key":"10.1016\/0304-3975(94)00181-H_BIB15","series-title":"Proc. 15th Ann. ACM Symp. on Theory of Computing","first-page":"94","article-title":"Multi-parity protocols","author":"Chandra","year":"1983"},{"key":"10.1016\/0304-3975(94)00181-H_BIB16","series-title":"Proc. 7th Symp. on Switching and Automata Theory","first-page":"78","article-title":"The recognition problem for the set of perfect squares","author":"Cobham","year":"1966"},{"key":"10.1016\/0304-3975(94)00181-H_BIB17","article-title":"Lower bounds for the complexity of 1-time-only branching programs","volume":"Vol. 199","author":"Dunne","year":"1985"},{"key":"10.1016\/0304-3975(94)00181-H_BIB18","series-title":"Proc. IEEE Internat. Conf. on Computer Aided Design ICCAD-88","first-page":"2","article-title":"Evaluation and improvements of Boolean comparison method based on binary decision diagrams","author":"Fujita","year":"1988"},{"key":"10.1016\/0304-3975(94)00181-H_BIB19","series-title":"Proc. Conf. Automata, Languages, and Programming","first-page":"227","article-title":"The complexity of equivalence and containment for free single variable program schemes","volume":"Vol. 62","author":"Fortune","year":"1978"},{"key":"10.1016\/0304-3975(94)00181-H_BIB20","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1109\/12.53586","article-title":"Finding the optimal variable ordering for binary decision diagrams","volume":"39","author":"Friedman","year":"1990","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0304-3975(94)00181-H_BIB21","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0890-5401(92)90046-I","article-title":"Branching programs provide lower bounds on the areas of multilective deterministic and nondeterministic VLSI circuits","volume":"96","author":"Hromkovic","year":"1992","journal-title":"Inform. and Comput."},{"issue":"3","key":"10.1016\/0304-3975(94)00181-H_BIB22","article-title":"Exponential lower bounds on the complexity of real-time and local branching programs","volume":"24","author":"Krause","year":"1988","journal-title":"J. Inform. Process. Cybernet"},{"key":"10.1016\/0304-3975(94)00181-H_BIB23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(91)90072-A","article-title":"Lower bounds for depth-restricted branching programs","volume":"91","author":"Krause","year":"1991","journal-title":"Inform. and Comput."},{"key":"10.1016\/0304-3975(94)00181-H_BIB24","series-title":"Proc. FCT' 87","article-title":"Exponential lower bounds for real-time branching programs","volume":"Vol. 278","author":"Kriegel","year":"1987"},{"key":"10.1016\/0304-3975(94)00181-H_BIB25","first-page":"11","article-title":"Complexity estimate of Boolean function computation by simplest types of binary programs","volume":"Vol. 29","author":"Kuzmin","year":"1976"},{"key":"10.1016\/0304-3975(94)00181-H_BIB26","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1002\/j.1538-7305.1959.tb01585.x","article-title":"Representation of switching circuits by binary decision programs","volume":"38","author":"Lee","year":"1959","journal-title":"Bell Systems Techn. J."},{"key":"10.1016\/0304-3975(94)00181-H_BIB27","series-title":"Proc. IEEE Internat. Conf. on Computer Aided Design ICCAD-88","first-page":"6","article-title":"Logic verification using binary decision diagrams in a logic synthesis environment","author":"Malik","year":"1988"},{"key":"10.1016\/0304-3975(94)00181-H_BIB28","series-title":"Proc. IEEE Internat. Symp. on Circuits and Systems","first-page":"210","article-title":"Mapping of binary decision diagrams into silicon","author":"Matos","year":"1983"},{"key":"10.1016\/0304-3975(94)00181-H_BIB29","series-title":"Proc. Mathematical Foundations of Computer Science","first-page":"61","article-title":"Restricted branching programs and their computational power","volume":"Vol. 452","author":"Meinel","year":"1990"},{"key":"10.1016\/0304-3975(94)00181-H_BIB30","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0890-5401(90)90046-K","article-title":"Polynomial size \u03a9-branching progams and their computational power","volume":"85","author":"Meinel","year":"1992","journal-title":"Inform. and Comput."},{"key":"10.1016\/0304-3975(94)00181-H_BIB31","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1145\/356893.356898","article-title":"Decision trees and diagrams","volume":"14","author":"Moret","year":"1982","journal-title":"ACM Comput. Surveys"},{"key":"10.1016\/0304-3975(94)00181-H_BIB32","first-page":"480","article-title":"A lower bound on complexity of branching programs","volume":"Vol. 176","author":"Pudl\u00e1k","year":"1984"},{"key":"10.1016\/0304-3975(94)00181-H_BIB33","series-title":"The Complexity of Computing","author":"Savage","year":"1976"},{"key":"10.1016\/0304-3975(94)00181-H_BIB34","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/S0019-9958(84)80031-5","article-title":"Optimal decision trees and one-time only branching programs for symmetric Boolean functions","volume":"62","author":"Wegener","year":"1984","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(94)00181-H_BIB35","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0022-0000(86)90004-8","article-title":"Time-space trade-offs for branching programs","volume":"32","author":"Wegener","year":"1986","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(94)00181-H_BIB36","series-title":"The Complexity of Boolean Functions","author":"Wegener","year":"1987"},{"key":"10.1016\/0304-3975(94)00181-H_BIB37","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1145\/42282.46161","article-title":"On the complexity of branching Functions and decision trees for clique functions","volume":"35","author":"Wegener","year":"1988","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0304-3975(94)00181-H_BIB38","series-title":"Proc. Mathematical Foundations of Computer Science","first-page":"562","article-title":"An exponential lower bound for one-time-only branching programs","volume":"Vol. 176","author":"Z\u00e1k","year":"1984"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759400181H?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759400181H?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T12:49:01Z","timestamp":1777553341000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759400181H"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":39,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["030439759400181H"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(94)00181-h","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1995,7]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"On the size of binary decision diagrams representing Boolean functions","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/0304-3975(94)00181-H","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1995 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}