{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:45:25Z","timestamp":1770972325421,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642403125","type":"print"},{"value":"9783642403132","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40313-2_59","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T10:36:43Z","timestamp":1376649403000},"page":"667-678","source":"Crossref","is-referenced-by-count":4,"title":["Arithmetic Branching Programs with Memory"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Mengel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"59_CR1","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A. Barrington","year":"1989","unstructured":"Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. Journal of Computer and System Sciences\u00a038(1), 150\u2013164 (1989)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"59_CR2","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0221006","volume":"21","author":"M. Ben-Or","year":"1992","unstructured":"Ben-Or, M., Cleve, R.: Computing algebraic formulas using a constant number of registers. SIAM J. Comput.\u00a021(1), 54\u201358 (1992)","journal-title":"SIAM J. Comput."},{"key":"59_CR3","unstructured":"Brent, R.P.: The complexity of multiple-precision arithmetic. In: Brent, R.P., Andersson, R.S. (eds.) The Complexity of Computational Problem Solving, pp. 126\u2013165. Univ. of Queensland Press (1976)"},{"key":"59_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-3-642-03816-7_17","volume-title":"Mathematical Foundations of Computer Science 2009","author":"I. Briquel","year":"2009","unstructured":"Briquel, I., Koiran, P.: A dichotomy theorem for polynomial evaluation. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 187\u2013198. Springer, Heidelberg (2009)"},{"key":"59_CR5","doi-asserted-by":"crossref","unstructured":"B\u00fcrgisser, P.: Completeness and reduction in algebraic complexity theory. Springer (2000)","DOI":"10.1007\/978-3-662-04179-6"},{"key":"59_CR6","first-page":"158","volume":"17","author":"S. Kintali","year":"2010","unstructured":"Kintali, S.: Realizable paths and the NL vs L problem. Electronic Colloquium on Computational Complexity (ECCC)\u00a017, 158 (2010)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"59_CR7","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2012.03.041","volume":"448","author":"P. Koiran","year":"2012","unstructured":"Koiran, P.: Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci.\u00a0448, 56\u201365 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"59_CR8","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.jco.2006.09.006","volume":"24","author":"G. Malod","year":"2008","unstructured":"Malod, G., Portier, N.: Characterizing Valiant\u2019s algebraic complexity classes. J. Complexity\u00a024(1), 16\u201338 (2008)","journal-title":"J. Complexity"},{"key":"59_CR9","doi-asserted-by":"crossref","unstructured":"Mengel, S.: Arithmetic Branching Programs with Memory, arXiv:1303.1969 (2013)","DOI":"10.1007\/978-3-642-40313-2_59"},{"key":"59_CR10","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Lower bounds for non-commutative computation. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, p. 418. ACM (1991)","DOI":"10.1145\/103418.103462"},{"issue":"2","key":"59_CR11","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1145\/3149.3158","volume":"32","author":"S. Skyum","year":"1985","unstructured":"Skyum, S., Valiant, L.G.: A complexity theory based on boolean algebra. J. ACM\u00a032(2), 484\u2013502 (1985)","journal-title":"J. ACM"},{"issue":"1","key":"59_CR12","first-page":"116","volume":"75","author":"S. Toda","year":"1992","unstructured":"Toda, S.: Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Transactions on Information and Systems\u00a075(1), 116\u2013124 (1992)","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"4","key":"59_CR13","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L.G. Valiant","year":"1983","unstructured":"Valiant, L.G., Skyum, S., Berkowitz, S., Rackoff, C.: Fast parallel computation of polynomials using few processors. SIAM J. Comput.\u00a012(4), 641\u2013644 (1983)","journal-title":"SIAM J. Comput."},{"key":"59_CR14","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, pp. 249\u2013261. ACM (1979)","DOI":"10.1145\/800135.804419"},{"issue":"4","key":"59_CR15","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s00224-006-1312-0","volume":"40","author":"V. Weber","year":"2007","unstructured":"Weber, V., Schwentick, T.: Dynamic complexity theory revisited. Theory Comput. Syst.\u00a040(4), 355\u2013377 (2007)","journal-title":"Theory Comput. Syst."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40313-2_59","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T22:09:52Z","timestamp":1558303792000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40313-2_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403125","9783642403132"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40313-2_59","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}