{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T02:10:23Z","timestamp":1736129423534,"version":"3.32.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":31,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540529535"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029596","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T05:33:46Z","timestamp":1133415226000},"page":"61-75","source":"Crossref","is-referenced-by-count":1,"title":["Restricted branching programs and their computational power"],"prefix":"10.1007","author":[{"given":"Christoph","family":"Meinel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"M.Ajtai, L.Babai, P.Hajnal, J.Komlos, P.Pudlak, V.R\u00f6dl, E.Szemeredi G.Turan: Two Lower Bounds for Branching Programs, Proc. 18.ACM STOC (1986), 30\u201338.","DOI":"10.1145\/12130.12134"},{"key":"5_CR2","unstructured":"A.E.Andreev: On a Method of Obtaining Lower Bounds for the Complexity of Individual Montone Functions, Dokl. Akad. Nauk SSSR 282\/5, 1033\u20131037."},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"D.A.Barrington: Bounded-width Polynomial Size Branching Programs Recognize Exactly those Languages in NC1, Proc. 18. ACM STOC, 1\u20135.","DOI":"10.1145\/12130.12131"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"A.Cobham: The Recognition Problem for the Set of Perfect Squares, Research paper RC-1704, IBM Watson Research Centre, 1966.","DOI":"10.1109\/SWAT.1966.30"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"C.Damm, Ch.Meinel: Separating Completely Complexity Classes Related to Polynomial Size \u03a9-Decision Trees, Proc. FCT'89, LNCS 380, 127\u2013136.","DOI":"10.1007\/3-540-51498-8_12"},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"M.Furst, J.B.Saxe, M.Sipser: Parity, Circuits, and the Polynomial Time Hierarchy, Proc. 22. IEEE FOCS, 1981, 260\u2013270.","DOI":"10.1109\/SFCS.1981.35"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"J.Hastad: Improved Lower Bounds for Small Depth Circuits, Proc. 18.ACM STOC (1986), 6\u201320.","DOI":"10.1145\/12130.12132"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"N.Immerman: Nondeterministic Space is Closed Under Complement, Techn. Report 552, Yale Univ., 1987.","DOI":"10.1109\/SCT.1988.5270"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"R.M.Karp, R.J.Lipton: Some Connections Between Nonuniform and Uniform Complexity Classes, Proc. 12.ACM STOC (1980), 302\u2013309.","DOI":"10.1145\/800141.804678"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"K.Kriegel, S.Waack: Exponential Lower Bounds for Real-time Branching Programs, Proc. FCT'87, LNCS 278, 263\u2013267.","DOI":"10.1007\/3-540-18740-5_55"},{"key":"5_CR11","unstructured":"M.Krause: Separating \u2295L from L, NL, co-NL, and AL for oblivious Turing Machines of Linear Access-Time, This volume."},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"M.Krause, Ch.Meinel, S.Waack: Separating the Eraser Turing Machine Classes L e , NL e , co-NL e and P e , Proc. MFCS'88, LNCS 324, 405\u2013413.","DOI":"10.1007\/BFb0017163"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"M.Krause, Ch.Meinel, S.Waack: Separating Complexity Classes Related to Restricted Logarithmic Space-Bounded Turing Machines, Proc. 4th Structure in Complexity Theory (Eugene, USA), 240\u2013259.","DOI":"10.1109\/SCT.1989.41831"},{"key":"5_CR14","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1002\/j.1538-7305.1959.tb01585.x","volume":"38","author":"C.Y. Lee","year":"1959","unstructured":"C.Y. Lee: Representation of Switching Functions by Binary Decision Programs, Bell System Techn. Journal 38 (1959), 985\u2013999.","journal-title":"Bell System Techn. Journal"},{"key":"5_CR15","unstructured":"W.Masek: A Fast Algorithm for the String Editing Problem and Decision Graph Complexity, M.Sc. thesis, MIT, 1976."},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Ch.Meinel: P-projection Reducibility and the Complexity Classes L(nonuniform) and NL(nonuniform), Proc. MFCS'86, LNCS 233, 527\u2013535.","DOI":"10.1007\/BFb0016279"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Ch.Meinel: The Power of Nondeterminism in Polynomial-size Bounded-width Branching Programs, Proc. FCT'87, LNCS 278, 302\u2013309.","DOI":"10.1007\/3-540-18740-5_65"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Ch.Meinel: The Power of Polynomial Size \u03a9-branching Programs, Proc. STACS'88, Bordeaux, LNCS 294, 81\u201390.","DOI":"10.1007\/BFb0035834"},{"key":"5_CR19","unstructured":"Ch.Meinel: Modified branching Programs and their Computational Power, (Habilitation Thesis) LNCS 370."},{"key":"5_CR20","unstructured":"E.I.Nechiporuk: A Boolean Function, Sov. Math. Dokl., No.7, 1966, 999\u20131000."},{"key":"5_CR21","doi-asserted-by":"crossref","first-page":"163","DOI":"10.2307\/2370324","volume":"43","author":"E. Post","year":"1921","unstructured":"E. Post: Introduction to a General Theory of Elementary Propositions, Am. J. Math. 43 (1921), 163\u2013185.","journal-title":"Am. J. Math."},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"P.Pudlak: A Lower Bound on Complexity of Branching Programs, Proc. MFCS'84, LNCS 176, 480\u2013489.","DOI":"10.1007\/BFb0030331"},{"key":"5_CR23","unstructured":"P.Pudlak, S.\u017dak: Space Complexity of Computations, Preprint Univ. of Prague, 1983."},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"A.A.Razborov: A Lower Bound for the Monotone Network Complexity of the Logical Permanent, Matem. Zametki 37\/6.","DOI":"10.1007\/BF01157687"},{"key":"5_CR25","unstructured":"A.A.Razborov: Lower Bounds on the Size of Bounded-depth Networks over the Basis {#x22C0;,\u2295}, Techn. Preprint Steklov Inst. Moskau, 1986."},{"issue":"3","key":"5_CR26","first-page":"236","volume":"22","author":"W. Ruzzo","year":"1981","unstructured":"W. Ruzzo: On Uniform Circuit Complexity, JCSS 22 (3), 1981, 236\u2013283.","journal-title":"JCSS"},{"key":"5_CR27","first-page":"96","volume":"33","author":"R. Szelepcsenyi","year":"1987","unstructured":"R. Szelepcsenyi: The Method of Forcing for Nondeterministic Automata, Bull. EATCS 33, 96\u201399, 1987.","journal-title":"Bull. EATCS"},{"key":"5_CR28","doi-asserted-by":"crossref","unstructured":"I.Wegener: Optimal Decision Trees and 1-Time Only Branching Programs for Symmetric Boolean Functions, Proc. 9th CAAP, 1984.","DOI":"10.1016\/S0019-9958(84)80031-5"},{"issue":"2","key":"5_CR29","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1145\/42282.46161","volume":"35","author":"I. Wegener","year":"1988","unstructured":"I. Wegener: On the Complexity of Branching Programs and Decision Trees for Clique Functions, JACM Vol. 35, No. 2 (1988), 461\u2013471.","journal-title":"JACM"},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"A.C.Yao: Separating the Polynomial-time hierarchy by Oracles, Proc. 26.IEEE FOCS (1985), 1\u201310.","DOI":"10.1109\/SFCS.1985.49"},{"key":"5_CR31","doi-asserted-by":"crossref","unstructured":"S.\u017dak: An Exponential Lower Bound for One-time-only Branching Programs, Proc. MFCS'84, LNCS 176, 562\u2013566.","DOI":"10.1007\/BFb0030340"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1990"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0029596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T01:34:31Z","timestamp":1736127271000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540529535"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/bfb0029596","relation":{},"subject":[]}}