{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,11]],"date-time":"2025-04-11T05:11:09Z","timestamp":1744348269022},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648277"},{"type":"electronic","value":"9783540685326"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055813","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T13:36:31Z","timestamp":1155821791000},"page":"625-635","source":"Crossref","is-referenced-by-count":2,"title":["Optimizing OBDDs is still intractable for monotone functions"],"prefix":"10.1007","author":[{"given":"Kazuo","family":"Iwama","sequence":"first","affiliation":[]},{"given":"Mitsushi","family":"Nozoe","sequence":"additional","affiliation":[]},{"given":"Shuzo","family":"Yajima","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"issue":"1","key":"60_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"N.Alon and R.B.Boppana: The monotone circuit complexity of Boolean functions, Combinatorica 7(1)a, pp.1\u201322 (1987).","journal-title":"Combinatorica"},{"issue":"No.9","key":"60_CR2","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1109\/12.537122","volume":"45","author":"B. Bollig","year":"1996","unstructured":"B.Bollig and I.Wegener: Improving the variable ordering of OBDDs Is NP-complete, IEEE Trans. Comput. Vol.45,No.9,pp.993\u20131002(1996).","journal-title":"IEEE Trans. Comput."},{"issue":"N0.8","key":"60_CR3","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"C35","author":"R.E. Bryant","year":"1986","unstructured":"R.E.Bryant: Graph-based algorithms for Boolean function manipulation, IEEE Trans. Comput. Vol.C35,N0.8,pp.677\u2013691(1986).","journal-title":"IEEE Trans. Comput."},{"key":"60_CR4","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"M.R.Garey, D.S.Johnson and L.Stockmeyer: Some simplified NP-complete graph problems, Theoretical Computer Science, Vol.1, pp.237\u2013267(1976).","journal-title":"Theoretical Computer Science"},{"key":"60_CR5","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0304-3975(97)83807-8","volume":"180","author":"K. Hosaka","year":"1997","unstructured":"K.Hosaka, Y.Takenaga, T. Kaneda and S. Yajima: Size of ordered binary decision diagrams representing threshold functions, Theoret. Comput. Sci.180,pp.47\u201360 (1997).","journal-title":"Theoret. Comput. Sci."},{"key":"60_CR6","unstructured":"S.Jukuna, A.Razborov, P.Savicky and I.Wegener: On P versus NP\u2229co-NP for decision trees and read-once branching problems, Proc.27nd MFCS, pp.319\u2013326 (1997)."},{"key":"60_CR7","doi-asserted-by":"crossref","unstructured":"M.R.Mercer, R.Kapur and D.E.Ross: Functional approached to generating orderings for efficient symbolic representation, Proc. 29th ACM\/IEEE Design Automation Conference, pp.614\u2013619 (1992).","DOI":"10.1109\/DAC.1992.227810"},{"key":"60_CR8","unstructured":"S.Muroga: Threshold logic and its applications, John Wiley & Sons (1971)."},{"issue":"1","key":"60_CR9","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"C.E. Shannon","year":"1949","unstructured":"C.E.Shannon: The synthesis of two-terminal switching circuits, Bell Systems Tech.J. 28(1),pp.59\u201398(1949).","journal-title":"Bell Systems Tech.J."},{"issue":"No.4","key":"60_CR10","first-page":"271","volume":"E79-D","author":"S. Tani","year":"1996","unstructured":"S. Tani, K. Hamaguchi and S. Yajima: The complexity of the optimal variable ordering problems of a shared binary decision diagram, IEICE Trans.Inf.& Syst., Vol.E79-D,No.4,pp.271\u2013281(1996).Also, in Proc.ISAAC93.","journal-title":"IEICE Trans.Inf.& Syst."},{"issue":"No.1","key":"60_CR11","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02122563","volume":"8","author":"E. Tardos","year":"1988","unstructured":"E. Tardos: The gap between monotone and non-monotone circuit complexity is exponential, Combinatorica, Vol.8,No.1,pp.141\u2013142(1988).","journal-title":"Combinatorica"},{"issue":"No.3","key":"60_CR12","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1137\/0220032","volume":"20","author":"U. Zwick","year":"1991","unstructured":"U.Zwick: A 4n lower bound on the combinational complexity of certain symmetric Boolean functions over the basis of unate dyadic Boolean functions, SIAM J. COMPUT., Vol.20,No.3,pp.499\u2013505(1991).","journal-title":"SIAM J. COMPUT."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1998"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055813","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,11]],"date-time":"2019-02-11T18:01:17Z","timestamp":1549908077000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055813"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/bfb0055813","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}