{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:28:25Z","timestamp":1759638505934,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319155784"},{"type":"electronic","value":"9783319155791"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-15579-1_35","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T08:36:13Z","timestamp":1424680573000},"page":"449-460","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Complexity of Regular Functions"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[]},{"given":"Ian","family":"Mertz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"35_CR1","unstructured":"Allender, E.: Arithmetic circuits and counting complexity classes. In: Kraj\u00ed\u010dek, J. (ed.) Complexity of Computations and Proofs, Quaderni di Matematica, vol. 13, pp. 33\u201372. Seconda Universit\u00e0 di Napoli (2004)"},{"issue":"1\u20132","key":"35_CR2","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0304-3975(97)00227-2","volume":"209","author":"E Allender","year":"1998","unstructured":"Allender, E., Jiao, J., Mahajan, M., Vinay, V.: Non-commutative arithmetic circuits: Depth reduction and size lower bounds. Theoretical Computer Science 209(1\u20132), 47\u201386 (1998)","journal-title":"Theoretical Computer Science"},{"key":"#cr-split#-35_CR3.1","unstructured":"Alur, R.: Regular functions (2013)"},{"key":"#cr-split#-35_CR3.2","unstructured":"lecture presented at Horizons in TCS: A Celebration of Mihalis Yannakakis's 60th Birthday. Center for Computational Intractability, Princeton (2013)"},{"key":"35_CR4","unstructured":"Alur, R., Cern\u00fd, P.: Expressiveness of streaming string transducers. In: Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS). LIPIcs, vol. 8, pp. 1\u201312. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2010)"},{"key":"35_CR5","doi-asserted-by":"crossref","unstructured":"Alur, R., Cern\u00fd, P.: Streaming transducers for algorithmic verification of single-pass list-processing programs. In: 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pp. 599\u2013610 (2011)","DOI":"10.1145\/1926385.1926454"},{"key":"35_CR6","unstructured":"Alur, R., D\u2019Antoni, L., Deshmukh, J.V., Raghothaman, M., Yuan, Y.: Regular functions, cost register automata, and generalized min-cost problems. CoRR abs\/1111.0670 (2011)"},{"key":"35_CR7","doi-asserted-by":"crossref","unstructured":"Alur, R., D\u2019Antoni, L., Deshmukh, J.V., Raghothaman, M., Yuan, Y.: Regular functions and cost register automata. In: 28th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS), pp. 13\u201322 (2013). see also the expanded version [6]","DOI":"10.1109\/LICS.2013.65"},{"key":"35_CR8","doi-asserted-by":"crossref","unstructured":"Alur, R., Freilich, A., Raghothaman, M.: Regular combinators for string transformations. In: Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic and the Twenty-Ninth Annual ACM\/IEEE Symposium on Logic in Computer Science, (CSL-LICS), p. 9. ACM (2014)","DOI":"10.1145\/2603088.2603151"},{"key":"35_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-39212-2_7","volume-title":"Automata, Languages, and Programming","author":"R Alur","year":"2013","unstructured":"Alur, R., Raghothaman, M.: Decision\u00a0problems\u00a0for\u00a0additive\u00a0regular\u00a0functions. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 37\u201348. Springer, Heidelberg (2013)"},{"key":"35_CR10","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"DA Barrington","year":"1989","unstructured":"Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC$$^1$$. Journal of Computer and System Sciences 38, 150\u2013164 (1989)","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0028550","volume-title":"STACS 98","author":"DA Mix Barrington","year":"1998","unstructured":"Mix Barrington, D.A., Lu, C.-J., Miltersen, P.B., Skyum, S.: Searching constant width mazes captures the AC$$^0$$ hierarchy. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 73\u201383. Springer, Heidelberg (1998)"},{"issue":"1","key":"35_CR12","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 Journal on Computing 21(1), 54\u201358 (1992)","journal-title":"SIAM Journal on Computing"},{"key":"35_CR13","unstructured":"Buss, S.: Comment on formula evaluation (2014); personal communication"},{"issue":"4","key":"35_CR14","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1137\/0221046","volume":"21","author":"SR Buss","year":"1992","unstructured":"Buss, S.R., Cook, S., Gupta, A., Ramachandran, V.: An optimal parallel algorithm for formula evaluation. SIAM Journal on Computing 21(4), 755\u2013780 (1992)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"35_CR15","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1006\/jcss.1998.1588","volume":"57","author":"H Caussinus","year":"1998","unstructured":"Caussinus, H., McKenzie, P., Th\u00e9rien, D., Vollmer, H.: Nondeterministic NC$$^{\\text{1 }}$$ computation. Journal of Computer and System Sciences 57(2), 200\u2013212 (1998)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"35_CR16","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1145\/371316.371512","volume":"2","author":"J Engelfriet","year":"2001","unstructured":"Engelfriet, J., Hoogeboom, H.J.: MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Log. 2(2), 216\u2013254 (2001)","journal-title":"ACM Trans. Comput. Log."},{"key":"35_CR17","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1016\/S0022-0000(02)00025-9","volume":"65","author":"W Hesse","year":"2002","unstructured":"Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences 65, 695\u2013716 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR18","doi-asserted-by":"crossref","unstructured":"Kiefer, S., Murawski, A.S., Ouaknine, J., Wachter, B., Worrell, J.: On the complexity of equivalence and minimisation for Q-weighted automata. Logical Methods in Computer Science 9(1) (2013)","DOI":"10.2168\/LMCS-9(1:8)2013"},{"key":"35_CR19","doi-asserted-by":"crossref","unstructured":"Vinay, V.: Counting auxiliary pushdown automata. In: Proceedings of the Sixth Annual Structure in Complexity Theory Conference, June 30-July 3, Chicago, Illinois, USA, pp. 270\u2013284 (1991). http:\/\/dx.doi.org\/10.1109\/SCT.1991.160269","DOI":"10.1109\/SCT.1991.160269"},{"key":"35_CR20","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York Inc. (1999)","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15579-1_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T22:37:44Z","timestamp":1676932664000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-15579-1_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319155784","9783319155791"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15579-1_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 February 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}