{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:47:44Z","timestamp":1725662864415},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540088608"},{"type":"electronic","value":"9783540358077"}],"license":[{"start":{"date-parts":[[1978,1,1]],"date-time":"1978-01-01T00:00:00Z","timestamp":252460800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1978]]},"DOI":"10.1007\/3-540-08860-1_11","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T11:33:30Z","timestamp":1330169610000},"page":"125-141","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Size \u2014 Depth tradeoff in boolean formulas"],"prefix":"10.1007","author":[{"given":"Beate","family":"Commentz-Walter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R. P. Brent","year":"1974","unstructured":"Brent, R.P.: The Parallel Evaluation of General Arithmetic Expressions, JACM 21, pp. 201\u2013206, 1974.","journal-title":"JACM"},{"key":"11_CR2","first-page":"83","volume-title":"Proc. Symposium on Complexity and Parallel Numerical Algorithms","author":"R. P. Brent","year":"1973","unstructured":"Brent, R.P.: The Parallel Evaluation of Arithmetic Expressions in Logarithmic Time, Proc. Symposium on Complexity and Parallel Numerical Algorithms (May 1973), Academic Press, New York, pp. 83\u2013102"},{"key":"11_CR3","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1109\/T-C.1973.223757","volume":"22","author":"R. P. Brent","year":"1973","unstructured":"Brent, R.P., Kuck, D.J., Maruyama, K.M.: The Parallel Evaluation of Arithmetic Expressions without Division, IEEE Trans. Comp. C. 22, pp. 532\u2013534, May 1973","journal-title":"IEEE Trans. Comp. C."},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Fischer, M.J., Mayer, A.R., Paterson, M.S.: Lower Bounds on the Size of Boolean Formulas, ACM, Proc. pp. 37\u201344, 1975","DOI":"10.1145\/800116.803751"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Hodes, L., Specker, E.: Length of Formulas and Elimination of Quantifiers I, Contributions to Math. Logic, ed. K. Sch\u00fctte, North Holland Publ. Co., pp. 175\u2013188, 1968 (appears in [18])","DOI":"10.1016\/S0049-237X(08)70524-X"},{"issue":"1","key":"11_CR6","first-page":"35","volume":"9","author":"V. M. Krapchenko","year":"1971","unstructured":"Krapchenko, V.M.: On the Complexity of the Realization of the Linear Function in the Class cf II-circuits, Math. Zametki 9, 1(1971), pp. 35\u201340 (Russian, a translation appears in reference 15 below).","journal-title":"Math. Zametki"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/BF01070501","volume":"6","author":"O. B. Lupanov","year":"1970","unstructured":"Lupanov, O.B.: Effect on the Depth of Formulas on their Complexity, Cybernetics 6, pp. 62\u201366, 1970","journal-title":"Cybernetics"},{"key":"11_CR8","unstructured":"McColl, W.F.: Some Results on Circuit Depth, Report No. 18, Comp. Science Dept., University of Warwick, March 1977"},{"key":"11_CR9","volume-title":"Effiziente Algorithmen","author":"K. Mehlhorn","year":"1977","unstructured":"Mehlhorn, K.: Effiziente Algorithmen, Teubner Studienb\u00fccher, Stuttgart, 1977"},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1145\/321958.321973","volume":"23","author":"D. E. Muller","year":"1976","unstructured":"Muller, D.E.: Preparata F.P., Restructing of Arithmetic Expressions for Parallel Evaluation, JACM Vol. 23, pp.534\u2013543, July 1976","journal-title":"JACM"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Muller, D.E.: Preparata F.P., Efficient Parallel Evaluation of Boolean Expression, IEEE Trans. C-25, pp. 548\u2013549","DOI":"10.1109\/TC.1976.1674647"},{"issue":"4","key":"11_CR12","first-page":"999","volume":"7","author":"E. I. Nechiporuk","year":"1966","unstructured":"Nechiporuk, E.I.: A Boolean Function, Soviet. Math. Doklady, Vol. 7, No. 4, pp. 999\u20131000, 1966 (compare [15], [17] and [18])","journal-title":"Soviet. Math. Doklady"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Paul, W.: N-Lower Bounds on the Combinational Complexity of Boolean Functions, ACM Proc., pp. 27\u201336, 1975","DOI":"10.1145\/800116.803750"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Pratt, V.R.: The Effect of Basis on Size of Boolean Expressions, SWAT, pp. 119\u2013121, 1975","DOI":"10.1109\/SFCS.1975.29"},{"key":"11_CR15","volume-title":"The Complexity of Computing","author":"J. E. Savage","year":"1976","unstructured":"Savage, J.E.: The Complexity of Computing, John Wiley & Sons, Inc., New York, 1976"},{"key":"11_CR16","unstructured":"Schnorr, C.P.: A 3n-Lower Bound on the Network Complexity of Boolean Functions, Preliminary Report, Universit\u00e4t Frankfurt, FB Mathematik, 1978"},{"key":"11_CR17","unstructured":"Spira, P.M.: On Time Hardware Complexity Tradeoffs for Boolean Functions, 4th Hawai Int. Symp. on Systems Science, pp. 525\u2013527, 1971 (compare [14])"},{"key":"11_CR18","unstructured":"Specker, E., Strassen, V.: Komplexit\u00e4t von Entscheidungsproblemen, Lecture Notes in Computer Science 43, Springer Verlag, pp. 182\u2013217"},{"key":"11_CR19","unstructured":"Commentz-Walter, B.: Tradeoff zwischen Gr\u00f6\u00dfe und Tiefe boolescher Formeln, Dissertation, Universit\u00e4t des Saarlandes, Math.-Nat.-Fakult\u00e4t, 1978, a translation to appear 1978"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08860-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T19:53:45Z","timestamp":1640894025000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08860-1_11"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1978]]},"ISBN":["9783540088608","9783540358077"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-08860-1_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1978]]},"assertion":[{"value":"26 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}