{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T19:43:16Z","timestamp":1781638996295,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540705741","type":"print"},{"value":"9783540705758","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_3","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"24-35","source":"Crossref","is-referenced-by-count":12,"title":["The Complexity of Boolean Formula Minimization"],"prefix":"10.1007","author":[{"given":"David","family":"Buchfuhrer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christopher","family":"Umans","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"3_CR1","volume-title":"Logic synthesis","author":"S. Devadas","year":"1994","unstructured":"Devadas, S., Ghosh, A., Keutzer, K.: Logic synthesis. McGraw-Hill, New York (1994)"},{"key":"3_CR2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"3_CR3","unstructured":"Hemaspaandra, E., Wechsung, G.: The minimization problem for Boolean formulas. In: FOCS, pp. 575\u2013584 (1997)"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Cai, J.-Y.: Circuit minimization problem. In: STOC, pp. 73\u201379 (2000)","DOI":"10.1145\/335305.335314"},{"key":"3_CR5","first-page":"125","volume-title":"FOCS","author":"A.R. Meyer","year":"1972","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: FOCS, pp. 125\u2013129. IEEE, Los Alamitos (1972)"},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy. Theor. Comput. Sci.\u00a03(1), 1\u201322 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR7","unstructured":"Umans, C.: The minimum equivalent DNF problem and shortest implicants. In: FOCS, pp. 556\u2013563 (1998)"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Umans, C.: Hardness of approximating $\\Sigma_2^P$ minimization problems. In: FOCS, pp. 465\u2013474 (1999)","DOI":"10.1109\/SFFCS.1999.814619"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1007\/3-540-48523-6_65","volume-title":"Automata, Languages and Programming","author":"C. Umans","year":"1999","unstructured":"Umans, C.: On the Complexity and Inapproximability of Shortest Implicant Problems. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol.\u00a01644, pp. 687\u2013696. Springer, Heidelberg (1999)"},{"issue":"7","key":"3_CR10","doi-asserted-by":"publisher","first-page":"1230","DOI":"10.1109\/TCAD.2005.855944","volume":"25","author":"C. Umans","year":"2006","unstructured":"Umans, C., Villa, T., Sangiovanni-Vincentelli, A.L.: Complexity of two-level logic minimization. IEEE Trans. on CAD of Integrated Circuits and Systems\u00a025(7), 1230\u20131246 (2006)","journal-title":"IEEE Trans. on CAD of Integrated Circuits and Systems"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:13:00Z","timestamp":1738325580000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}