{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:46:58Z","timestamp":1725536818077},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642038150"},{"type":"electronic","value":"9783642038167"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-03816-7_16","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T14:43:03Z","timestamp":1250692983000},"page":"175-186","source":"Crossref","is-referenced-by-count":1,"title":["Branching Programs for Tree Evaluation"],"prefix":"10.1007","author":[{"given":"Mark","family":"Braverman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Cook","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dustin","family":"Wehr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"16_CR1","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0211022","volume":"11","author":"A. Borodin","year":"1982","unstructured":"Borodin, A., Cook, S.: A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput.\u00a011(2), 287\u2013297 (1982)","journal-title":"SIAM J. Comput."},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"Borodin, A., Razborov, A., Smolensky, R.: On lower bounds for read-k-times branching programs. Computational Complexity\u00a03, 1\u201318 (1993)","journal-title":"Computational Complexity"},{"issue":"3","key":"16_CR3","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0022-0000(74)80046-2","volume":"9","author":"S. Cook","year":"1974","unstructured":"Cook, S.: An observation on time-storage trade off. J. Comput. Syst. Sci.\u00a09(3), 308\u2013316 (1974)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0022-0000(76)80048-7","volume":"13","author":"S. Cook","year":"1976","unstructured":"Cook, S., Sethi, R.: Storage requirements for deterministic polynomial time recognizable languages. J. Comput. Syst. Sci.\u00a013(1), 25\u201337 (1976)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"16_CR5","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00224-007-9049-y","volume":"43","author":"A. G\u00e1l","year":"2008","unstructured":"G\u00e1l, A., Kouck\u00fd, M., McKenzie, P.: Incremental branching programs. Theory Comput. Syst.\u00a043(2), 159\u2013184 (2008)","journal-title":"Theory Comput. Syst."},{"key":"16_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106","volume-title":"Computational Complexity: A Conceptual Perspective","author":"O. Goldreich","year":"2008","unstructured":"Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge (2008)"},{"key":"#cr-split#-16_CR7.1","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Raz, R., Wigderson, A.: Super-logarithmic depth lower bounds via direct sum in communication complexity. Computational Complexity??5, 191???204 (1991);","DOI":"10.1007\/BF01206317"},{"key":"#cr-split#-16_CR7.2","unstructured":"An abstract appeared in the 6th Structure in Complexity Theory Conference (1991)"},{"key":"16_CR8","first-page":"30","volume":"91","author":"M. Mahajan","year":"2007","unstructured":"Mahajan, M.: Polynomial size log depth circuits: between NC 1and AC 1. Bulletin of the EATCS\u00a091, 30\u201342 (2007)","journal-title":"Bulletin of the EATCS"},{"key":"#cr-split#-16_CR9.1","doi-asserted-by":"crossref","unstructured":"Ne??iporuk, ??.: On a boolean function. Doklady of the Academy of the USSR??169(4), 765???766 (1966);","DOI":"10.1097\/00007890-196611000-00019"},{"key":"#cr-split#-16_CR9.2","unstructured":"English translation in Soviet Mathematics Doklady 7(4), 999???1000"},{"key":"16_CR10","unstructured":"Nordstr\u00f6m, J.: New wine into old wineskins: A survey of some pebbling classics with supplemental results (2009), http:\/\/people.csail.mit.edu\/jakobn\/research\/"},{"key":"16_CR11","first-page":"119","volume-title":"Record of Project MAC Conference on Concurrent Systems and Parallel Computations","author":"M. Paterson","year":"1970","unstructured":"Paterson, M., Hewitt, C.: Comparative schematology. In: Record of Project MAC Conference on Concurrent Systems and Parallel Computations, pp. 119\u2013128. ACM, New Jersey (1970)"},{"issue":"5","key":"16_CR12","first-page":"449","volume":"6","author":"P. Pudl\u00e1k","year":"1987","unstructured":"Pudl\u00e1k, P.: The hierarchy of boolean circuits. Computers and artificial intelligence\u00a06(5), 449\u2013468 (1987)","journal-title":"Computers and artificial intelligence"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Razborov, A.: Lower bounds for deterministic and nondeterministic branching programs. In: 8th Internat. Symp. on Fundamentals of Computation Theory, pp. 47\u201360 (1991)","DOI":"10.1007\/3-540-54458-5_49"},{"issue":"3","key":"16_CR14","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"H. Sudborough","year":"1978","unstructured":"Sudborough, H.: On the tape complexity of deterministic context-free languages. J. ACM\u00a025(3), 405\u2013414 (1978)","journal-title":"J. ACM"},{"key":"#cr-split#-16_CR15.1","unstructured":"Taitslin, M.A.: An example of a problem from PTIME and not in NLogSpace. In: Proceedings of Tver State University (2005);"},{"key":"#cr-split#-16_CR15.2","unstructured":"Applied Mathematics, vol. 6(12) (2), pp. 5???22. Tver State University, Tver (2005)"},{"key":"16_CR16","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719789","volume-title":"Branching Programs and Binary Decision Diagrams","author":"I. Wegener","year":"2000","unstructured":"Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM Monographs on Discrete Mathematics and Applications. Soc. for Industrial and Applied Mathematics, Philadelphia (2000)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T02:33:55Z","timestamp":1558492435000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}