{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:40:13Z","timestamp":1742593213923,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540527534"},{"type":"electronic","value":"9783540471370"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52753-2_43","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:42:12Z","timestamp":1330206132000},"page":"242-253","source":"Crossref","is-referenced-by-count":0,"title":["\u03a9-branching programs of bounded width"],"prefix":"10.1007","author":[{"given":"Christoph","family":"Meinel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Barrington, D.A.: Bounded-width polynomial size branching programs recognize exactly those languages in in NC1. In: Proc. of 18th ACM STOC, 1986, pp. 1\u20135. (the journal version will appear in JACM).","DOI":"10.1145\/12130.12131"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Damm, C.\u2014 Meinel, Ch.: Separating complexity classes related to polynomial size \u03a9-decision trees completely. Proc. of FCT'89, Szeged, LNCS 380, 127\u2013136.","DOI":"10.1007\/3-540-51498-8_12"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Krause,M.\u2014 Meinel,Ch.\u2014 Waack,S.: Separating the eraser Turing machine classes \u2112e, NL e , co-NL e and P e. Proc. MFCS'88, Karlovy Vary, LNCS 324, pp. 405\u2013413.","DOI":"10.1007\/BFb0017163"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Krause,M.\u2014 Meinel,Ch.\u2014 Waack,S.: Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines. Proc. of 4. Structure in Complexity Theory, Eugene, IEEE Computer Press, 240\u2013249, 1989.","DOI":"10.1109\/SCT.1989.41831"},{"key":"15_CR5","unstructured":"Meinel,Ch.: p-projection reducibility and the complexity classes L(nonuniform) and NL(nonuniform). In: Proc. of MFCS'86, LNCS 233, pp. 527\u2013535. (the journal version can be found in: EIK 23 (1987), No. 10\/11, 545\u2013558.)"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Meinel,Ch.: The power of polynomial size \u03a9-branching programs. In: Proc. of STACS'88, Bordeaux, LNCS 294, pp. 81\u201390. (the journal version will appear in Information and Computation.)","DOI":"10.1007\/BFb0035834"},{"key":"15_CR7","unstructured":"Pudlak,P.\u2014 \u017dak,S.: Space complexity of computations, Preprint Univ. of Prague, 1983."},{"key":"15_CR8","volume-title":"The complexity of computing","author":"J.E. Savage","year":"1976","unstructured":"Savage, J.E.: The complexity of computing, Wiley, New York, 1976."},{"issue":"2","key":"15_CR9","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1145\/42282.46161","volume":"35","author":"I. Wegener","year":"1988","unstructured":"Wegener, I.: On the complexity of branching programs and decision trees for clique functions. In: JACM Vol. 35, No. 2 (1988), pp. 461\u2013471.","journal-title":"JACM"},{"key":"15_CR10","volume-title":"The Complexity of Boolean functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: The Complexity of Boolean functions, Wiley-Teubner, Stuttgart, 1987."}],"container-title":["Lecture Notes in Computer Science","CSL '89"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52753-2_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:03:33Z","timestamp":1742591013000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52753-2_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540527534","9783540471370"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-52753-2_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}