{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T23:40:08Z","timestamp":1748562008079,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662480564"},{"type":"electronic","value":"9783662480571"}],"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-662-48057-1_11","type":"book-chapter","created":{"date-parts":[[2015,8,10]],"date-time":"2015-08-10T01:29:54Z","timestamp":1439170194000},"page":"141-153","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Circuit Complexity Approach to Transductions"],"prefix":"10.1007","author":[{"given":"Micha\u00ebl","family":"Cadilhac","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Krebs","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Ludwig","sequence":"additional","affiliation":[]},{"given":"Charles","family":"Paperman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"DAM Barrington","year":"1989","unstructured":"Barrington, D.A.M.: Bounded-width polynomial size branching programs recognize exactly those languages in NC$$^1$$. J. Comp. Syst. Sc. 38, 150\u2013164 (1989)","journal-title":"J. Comp. Syst. Sc."},{"issue":"3","key":"11_CR2","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"DAM Barrington","year":"1992","unstructured":"Barrington, D.A.M., Compton, K., Straubing, H., Th\u00e9rien, D.: Regular languages in NC$$^1$$. J. Comput. Syst. Sci. 44(3), 478\u2013499 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1","volume-title":"Transductions and Context-Free Languages, Leitf\u00e4den der Angewandten Mathematik und Mechanik LAMM","author":"J Berstel","year":"1979","unstructured":"Berstel, J.: Transductions and Context-Free Languages, Leitf\u00e4den der Angewandten Mathematik und Mechanik LAMM. Teubner, Stuttgart (1979)"},{"issue":"1","key":"11_CR4","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/2462896.2462898","volume":"5","author":"O Beyersdorff","year":"2013","unstructured":"Beyersdorff, O., Datta, S., Krebs, A., Mahajan, M., Scharfenberger-Fabian, G., Sreenivasaiah, K., Thomas, M., Vollmer, H.: Verifying proofs in constant depth. TOCT 5(1), 2 (2013)","journal-title":"TOCT"},{"key":"11_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/978-3-662-43951-7_3","volume-title":"Automata, Languages, and Programming","author":"M Boja\u0144czyk","year":"2014","unstructured":"Boja\u0144czyk, M.: Transducers with Origin Information. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 26\u201337. Springer, Heidelberg (2014)"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Chaubard, L., Pin, J.\u00c9., Straubing, H.: First-order formulas with modular predicates. In: LICS, pp. 211\u2013220. IEEE (2006)","DOI":"10.1109\/LICS.2006.24"},{"issue":"1\u20133","key":"11_CR7","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0304-3975(88)90020-5","volume":"58","author":"C Choffrut","year":"1988","unstructured":"Choffrut, C., Sch\u00fctzenberger, M.P.: Counting with rational functions. Theor. Comput. Sci. 58(1\u20133), 81\u2013101 (1988)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/3-540-09510-1_8","volume-title":"Automata, Languages and Programming","author":"C Choffrut","year":"1979","unstructured":"Choffrut, C.: A generalization of Ginsburg and Rose\u2019s characterization of G-S-M mappings. In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol. 71, pp. 88\u2013103. Springer, Heidelberg (1979)"},{"issue":"1","key":"11_CR9","first-page":"1","volume":"16","author":"Z Esik","year":"2003","unstructured":"Esik, Z., Ito, M.: Temporal logic with cyclic counting and the degree of aperiodicity of finite automata. Acta Cybern. 16(1), 1\u201328 (2003)","journal-title":"Acta Cybern."},{"key":"11_CR10","unstructured":"Filiot, E., Krishna, S.N., Trivedi, A.: First-order definable string transformations. In: Raman, V., Suresh, S.P. (eds.) FSTTCS. LIPIcs, vol. 29, pp. 147\u2013159 (2014)"},{"key":"11_CR11","first-page":"13","volume":"17","author":"M Furst","year":"1984","unstructured":"Furst, M., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Theor. Comput. Syst. 17, 13\u201327 (1984)","journal-title":"Theor. Comput. Syst."},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Kouck\u00fd, M., Pudl\u00e1k, P., Th\u00e9rien, D.: Bounded-depth circuits: separating wires from gates. In: STOC, pp. 257\u2013265. ACM (2005)","DOI":"10.1145\/1060590.1060629"},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/3-540-49381-6_27","volume-title":"Algorithms and Computation","author":"K-J Lange","year":"1998","unstructured":"Lange, K.-J., McKenzie, P.: On the complexity of free monoid morphisms. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol. 1533, pp. 247\u2013255. Springer, Heidelberg (1998)"},{"issue":"4","key":"11_CR14","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1006\/jcss.2000.1742","volume":"62","author":"C Lautemann","year":"2001","unstructured":"Lautemann, C., McKenzie, P., Schwentick, T., Vollmer, H.: The descriptive complexity approach to LOGCFL. J. Comput. Syst. Sci. 62(4), 629\u2013652 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"01","key":"11_CR15","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1051\/ita:2005014","volume":"39","author":"J\u00c9 Pin","year":"2005","unstructured":"Pin, J.\u00c9., Straubing, H.: Some results on C-varieties. RAIRO-Theor. Inf. Appl. 39(01), 239\u2013262 (2005)","journal-title":"RAIRO-Theor. Inf. Appl."},{"issue":"1\u20132","key":"11_CR16","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0304-3975(94)00180-Q","volume":"145","author":"C Reutenauer","year":"1995","unstructured":"Reutenauer, C., Sch\u00fctzenberger, M.P.: Vari\u00e9t\u00e9s et fonctions rationnelles. Theor. Comput. Sci. 145(1\u20132), 229\u2013240 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9","volume-title":"Finite Automata, Formal Logic, and Circuit Complexity","author":"H Straubing","year":"1994","unstructured":"Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Boston (1994)"},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1007\/3-540-45995-2_46","volume-title":"LATIN 2002: Theoretical Informatics","author":"H Straubing","year":"2002","unstructured":"Straubing, H.: On logical descriptions of regular languages. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 528\u2013538. Springer, Heidelberg (2002)"},{"key":"11_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity","author":"H Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity. Springer-Verlag, Berlin (1999)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2015"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48057-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T23:00:46Z","timestamp":1748559646000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48057-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480564","9783662480571"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48057-1_11","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":"11 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}