{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T23:35:35Z","timestamp":1767137735630,"version":"build-2238731810"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031661587","type":"print"},{"value":"9783031661594","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-66159-4_2","type":"book-chapter","created":{"date-parts":[[2024,7,26]],"date-time":"2024-07-26T05:01:34Z","timestamp":1721970094000},"page":"13-21","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Polyregular Functions: Characterisations and Refutations"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4614-9444","authenticated-orcid":false,"given":"Sandra","family":"Kiefer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,27]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","unstructured":"Bojanczyk, M.: On the growth rates of polyregular functions. In: 38th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2023, Boston, MA, USA, 26\u201329 June 2023, pp. 1\u201313. IEEE (2023). https:\/\/doi.org\/10.1109\/LICS56636.2023.10175808","DOI":"10.1109\/LICS56636.2023.10175808"},{"key":"2_CR2","unstructured":"Boja\u0144czyk, M.: Polyregular functions. CoRR abs\/1810.08760 (2018). http:\/\/arxiv.org\/abs\/1810.08760"},{"key":"2_CR3","doi-asserted-by":"publisher","unstructured":"Boja\u0144czyk, M.: Folding interpretations. In: 38th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS), pp. 1\u201313 (2023). https:\/\/doi.org\/10.1109\/LICS56636.2023.10175796","DOI":"10.1109\/LICS56636.2023.10175796"},{"key":"2_CR4","doi-asserted-by":"publisher","unstructured":"Boja\u0144czyk, M., Klin, B.: Polyregular functions on unordered trees of bounded height. Proc. ACM Program. Lang. 8(POPL), 1326\u20131351 (2024). https:\/\/doi.org\/10.1145\/3632887","DOI":"10.1145\/3632887"},{"key":"2_CR5","doi-asserted-by":"publisher","unstructured":"Boja\u0144czyk, M.: Transducers of polynomial growth. In: Baier, C., Fisman, D. (eds.) LICS 2022: 37th Annual ACM\/IEEE Symposium on Logic in Computer Science, Haifa, Israel, 2\u20135 August 2022, pp. 1:1\u20131:27. ACM (2022). https:\/\/doi.org\/10.1145\/3531130.3533326","DOI":"10.1145\/3531130.3533326"},{"key":"2_CR6","doi-asserted-by":"publisher","unstructured":"Boja\u0144czyk, M., Kiefer, S., Lhote, N.: String-to-string interpretations with polynomial-size output. In: 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, 9\u201312 July 2019, Patras, Greece, pp. 106:1\u2013106:14 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.106","DOI":"10.4230\/LIPIcs.ICALP.2019.106"},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/3-540-08342-1_11","volume-title":"Automata, Languages and Programming","author":"MP Chytil","year":"1977","unstructured":"Chytil, M.P., J\u00e1kl, V.: Serial composition of 2-way finite-state transducers and simple programs on strings. In: Salomaa, A., Steinby, M. (eds.) ICALP 1977. LNCS, vol. 52, pp. 135\u2013147. Springer, Heidelberg (1977). https:\/\/doi.org\/10.1007\/3-540-08342-1_11"},{"key":"2_CR8","doi-asserted-by":"publisher","unstructured":"Colcombet, T., Dou\u00e9neau-Tabot, G., Lopez, A.: $$\\mathbb{Z}$$-polyregular functions. In: 38th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2023, Boston, MA, USA, 26\u201329 June 2023, pp. 1\u201313. IEEE (2023). https:\/\/doi.org\/10.1109\/LICS56636.2023.10175685","DOI":"10.1109\/LICS56636.2023.10175685"},{"key":"2_CR9","doi-asserted-by":"publisher","unstructured":"Dou\u00e9neau-Tabot, G.: Hiding pebbles when the output alphabet is unary. In: Boja\u0144czyk, M., Merelli, E., Woodruff, D.P. (eds.) 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, 4\u20138 July 2022, Paris, France. LIPIcs, vol.\u00a0229, pp. 120:1\u2013120:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2022.120","DOI":"10.4230\/LIPICS.ICALP.2022.120"},{"key":"2_CR10","unstructured":"Dou\u00e9neau-Tabot, G.: Optimization of string transducers. Ph.D. thesis, Universit\u00e9 Paris Cit\u00e9 (2023). https:\/\/gdoueneau.github.io\/pages\/phd.html"},{"issue":"7\u20138","key":"2_CR11","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/s00236-015-0224-3","volume":"52","author":"J Engelfriet","year":"2015","unstructured":"Engelfriet, J.: Two-way pebble transducers for partial functions and their composition. Acta Inform. 52(7\u20138), 559\u2013571 (2015). https:\/\/doi.org\/10.1007\/s00236-015-0224-3","journal-title":"Acta Inform."},{"key":"2_CR12","doi-asserted-by":"publisher","unstructured":"Engelfriet, J., Hoogeboom, H.J., Samwel, B.: XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles. Theor. Comput. Sci. 850, 40\u201397 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2020.10.030. Extended version of a PODS 2007 paper","DOI":"10.1016\/j.tcs.2020.10.030"},{"issue":"2","key":"2_CR13","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1006\/jcss.2001.1816","volume":"64","author":"J Engelfriet","year":"2002","unstructured":"Engelfriet, J., Maneth, S.: Output string languages of compositions of deterministic macro tree transducers. J. Comput. Syst. Sci. 64(2), 350\u2013395 (2002). https:\/\/doi.org\/10.1006\/jcss.2001.1816","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/3-540-45687-2_19","volume-title":"Mathematical Foundations of Computer Science 2002","author":"J Engelfriet","year":"2002","unstructured":"Engelfriet, J., Maneth, S.: Two-way finite state transducers with nested pebbles. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 234\u2013244. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45687-2_19"},{"issue":"9","key":"2_CR15","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s00236-003-0120-0","volume":"39","author":"J Engelfriet","year":"2003","unstructured":"Engelfriet, J., Maneth, S.: A comparison of pebble tree transducers with macro tree transducers. Acta Inform. 39(9), 613\u2013698 (2003). https:\/\/doi.org\/10.1007\/s00236-003-0120-0","journal-title":"Acta Inform."},{"issue":"3","key":"2_CR16","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/2984450.2984453","volume":"3","author":"E Filiot","year":"2016","unstructured":"Filiot, E., Reynier, P.A.: Transducers, logic and algebra for functions of finite words. ACM SIGLOG News 3(3), 4\u201319 (2016). https:\/\/doi.org\/10.1145\/2984450.2984453","journal-title":"ACM SIGLOG News"},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/BF00289513","volume":"1","author":"J Hartmanis","year":"1972","unstructured":"Hartmanis, J.: On non-determinancy in simple computing devices. Acta Inform. 1, 336\u2013344 (1972). https:\/\/doi.org\/10.1007\/BF00289513","journal-title":"Acta Inform."},{"issue":"2","key":"2_CR18","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/S0022-0000(71)80029-6","volume":"5","author":"OH Ibarra","year":"1971","unstructured":"Ibarra, O.H.: Characterizations of some tape and time complexity classes of turing machines in terms of multihead and auxiliary stack automata. J. Comput. Syst. Sci. 5(2), 88\u2013117 (1971). https:\/\/doi.org\/10.1016\/S0022-0000(71)80029-6","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR19","unstructured":"Jordon, L.: An investigation of feasible logical depth and complexity measures via automata and compression algorithms. Ph.D. thesis, National University of Ireland Maynooth (2022). https:\/\/mural.maynoothuniversity.ie\/16566\/"},{"key":"2_CR20","unstructured":"Kiefer, S., Nguy\u00ean, L.T.D., Pradic, C.: Refutations of pebble minimization via output languages (2023, submitted). https:\/\/arxiv.org\/abs\/2301.09234"},{"key":"2_CR21","unstructured":"Lopez, A.: Commutative N-polyregular functions (2024). https:\/\/arxiv.org\/abs\/2404.02232"},{"issue":"1","key":"2_CR22","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/S0022-0000(02)00030-2","volume":"66","author":"T Milo","year":"2003","unstructured":"Milo, T., Suciu, D., Vianu, V.: Typechecking for XML transformers. J. Comput. Syst. Sci. 66(1), 66\u201397 (2003). https:\/\/doi.org\/10.1016\/S0022-0000(02)00030-2. Journal version of a PODS 2000 paper","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR23","doi-asserted-by":"publisher","unstructured":"Muscholl, A., Puppis, G.: The many facets of string transducers. In: Niedermeier, R., Paul, C. (eds.) 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0126, pp. 2:1\u20132:21. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.2","DOI":"10.4230\/LIPIcs.STACS.2019.2"},{"key":"2_CR24","unstructured":"Nguy\u00ean, L.T.D.: Implicit automata in linear logic and categorical transducer theory. Ph.D. thesis, Universit\u00e9 Paris XIII (Sorbonne Paris Nord) (2021). https:\/\/theses.hal.science\/tel-04132636"},{"key":"2_CR25","doi-asserted-by":"publisher","unstructured":"Nguy\u00ean, L.T.D., No\u00fbs, C., Pradic, C.: Comparison-free polyregular functions. In: Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, 12\u201316 July 2021, Glasgow, Scotland (Virtual Conference). LIPIcs, vol.\u00a0198, pp. 139:1\u2013139:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2021.139","DOI":"10.4230\/LIPICS.ICALP.2021.139"},{"key":"2_CR26","doi-asserted-by":"publisher","unstructured":"Rawski, J., Dolatian, H., Heinz, J., Raimy, E.: Regular and polyregular theories of reduplication. Glossa: J. Gener. Linguist. 8(1) (2023). https:\/\/doi.org\/10.16995\/glossa.8885","DOI":"10.16995\/glossa.8885"},{"issue":"3","key":"2_CR27","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1051\/ita\/1986200302211","volume":"20","author":"B Rozoy","year":"1986","unstructured":"Rozoy, B.: Outils et r\u00e9sultats pour les transducteurs boustrophedons. RAIRO Theor. Inform. Appl. 20(3), 221\u2013249 (1986)","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"2_CR28","doi-asserted-by":"publisher","unstructured":"Strobl, L., Angluin, D., Chiang, D., Rawski, J., Sabharwal, A.: Transformers as transducers. CoRR abs\/2404.02040 (2024). https:\/\/doi.org\/10.48550\/ARXIV.2404.02040","DOI":"10.48550\/ARXIV.2404.02040"}],"updated-by":[{"DOI":"10.1007\/978-3-031-66159-4_21","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T00:00:00Z","timestamp":1729382400000}}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-66159-4_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T04:02:28Z","timestamp":1729310548000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-66159-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031661587","9783031661594"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-66159-4_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"27 July 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"20 October 2024","order":2,"name":"change_date","label":"Change Date","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"A correction has been published.","order":4,"name":"change_details","label":"Change Details","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The author has no competing interests to declare that are relevant to the content of this article","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"DLT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Developments in Language Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"G\u00f6ttingen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dlt2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}