{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:35Z","timestamp":1725663395051},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540176602"},{"type":"electronic","value":"9783540477464"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-17660-8_43","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T19:16:27Z","timestamp":1330197387000},"page":"1-12","source":"Crossref","is-referenced-by-count":1,"title":["On the complexity of branching programs and decision trees for clique functions"],"prefix":"10.1007","author":[{"given":"Ingo","family":"Wegener","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai,M.\/Babai,L.\/Hajnal,P.\/Koml\u00f3s,M.\/Pudl\u00e1k,P.\/R\u00f6dl,V.\/Szemer\u00e9di,E.\/Tur\u00e1n,G.: Two lower bounds for branching programs, 18. STOC, 30\u201338, 1986","DOI":"10.1145\/12130.12134"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Barrington,D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, 18.STOC,1\u20135, 1986","DOI":"10.1145\/12130.12131"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Borodin,A.\/Dolev,D.\/Fich,F.E.\/Paul,W.: Bounds for width two branching programs, 15.STOC, 87\u201393, 1983","DOI":"10.1145\/800061.808736"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Chandra,A.K.\/Furst,M.L.\/Lipton,R.J.: Multiparty protocols, 15.STOC, 94\u201399, 1983","DOI":"10.1145\/800061.808737"},{"key":"1_CR5","first-page":"90","volume":"199","author":"P. Dunne","year":"1985","unstructured":"Dunne, P.: Lower bounds on the complexity of 1-time only branching programs, FCT, LNCS 199, 90\u201399, 1985","journal-title":"FCT, LNCS"},{"key":"1_CR6","unstructured":"Erd\u00f6s,P.\/Kleitman,D.J.\/Rothschild,B.L.: Asymptotic enumeration of Kn-free graphs. Colloq.Intern.sulle Teorie Comb.,Accad.Naz. Lincei, Rome, 19\u201327, 1976"},{"key":"1_CR7","unstructured":"Kriegel,K.\/Waack,S.: Lower bounds on the complexity of real-time branching programs, Techn.Rep.,Akad.d.Wiss.Berlin (GDR), 1986"},{"key":"1_CR8","unstructured":"Masek,W.: A fast algorithm for the string editing problem and decision graph complexity, M.Sc. Thesis,MIT, 1976"},{"key":"1_CR9","first-page":"999","volume":"7","author":"E.I. Nechiporuk","year":"1966","unstructured":"Nechiporuk, E.I.: A Boolean function, Sov.Math.Dokl. 7, 999\u20131000, 1966","journal-title":"Sov.Math.Dokl."},{"key":"1_CR10","first-page":"480","volume":"176","author":"P. Pudl\u00e1k","year":"1984","unstructured":"Pudl\u00e1k, P.: A lower bound on complexity of branching programs, 11.MFCS,LNCS 176, 480\u2013489, 1984","journal-title":"11.MFCS,LNCS"},{"key":"1_CR11","unstructured":"Pudl\u00e1k,P.\/Z\u00e1k,S.: Space complexity of computations, Preprint, Univ. Prague, 1983"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0019-9958(84)80031-5","volume":"62","author":"I. Wegener","year":"1984","unstructured":"Wegener, I.: Optimal decision trees and one-time-only branching programs for symmetric Boolean functions, Information and Control 62, 129\u2013143, 1984","journal-title":"Information and Control"},{"key":"1_CR13","unstructured":"Wegener,I.: On the complexity of branching programs and decision trees for clique functions, Techn.Rep.,Univ.Frankfurt a.M., 1984"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0022-0000(86)90004-8","volume":"32","author":"I. Wegener","year":"1986","unstructured":"Wegener, I.: Time-space trade-offs for branching programs, Journal of Computer and System Sciences 32, 91\u201396, 1986","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Lower bounds by probabilistic arguments,24.FOCS, 420\u2013428, 1983","DOI":"10.1109\/SFCS.1983.30"}],"container-title":["Lecture Notes in Computer Science","TAPSOFT '87"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-17660-8_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:13:08Z","timestamp":1605643988000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-17660-8_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540176602","9783540477464"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-17660-8_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}