{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:18Z","timestamp":1750220658772,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T00:00:00Z","timestamp":1594166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["683080"],"award-info":[{"award-number":["683080"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,8]]},"DOI":"10.1145\/3373718.3394785","type":"proceedings-article","created":{"date-parts":[[2020,5,26]],"date-time":"2020-05-26T00:23:18Z","timestamp":1590452598000},"page":"252-265","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["First-order tree-to-tree functions"],"prefix":"10.1145","author":[{"given":"Miko\u0142aj","family":"Boja\u0144czyk","sequence":"first","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amina","family":"Doumane","sequence":"additional","affiliation":[{"name":"CNRS, ENS Lyon, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Alur. Streaming String Transducers. In Workshop on Logic, Language, Information and Computation, WoLLIC","volume":"6642","author":"Rajeev","year":"2011","unstructured":"Rajeev Alur. Streaming String Transducers. In Workshop on Logic, Language, Information and Computation, WoLLIC 2011 , Philadelphia, USA , volume 6642 of Lecture Notes in Computer Science, page 1. Springer, 2011. Rajeev Alur. Streaming String Transducers. In Workshop on Logic, Language, Information and Computation, WoLLIC 2011, Philadelphia, USA, volume 6642 of Lecture Notes in Computer Science, page 1. Springer, 2011."},{"key":"e_1_3_2_1_2_1","series-title":"LIPIcs","first-page":"1","volume-title":"Foundations of Software Technology and Theoretical Computer Science, FSTTCS","author":"Alur Rajeev","year":"2010","unstructured":"Rajeev Alur and Pavol \u010cern\u00fd . Expressiveness of streaming string transducers . In Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010 , Chennai, India , volume 8 of LIPIcs , pages 1 -- 12 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik , 2010. Rajeev Alur and Pavol \u010cern\u00fd. Expressiveness of streaming string transducers. In Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, Chennai, India, volume 8 of LIPIcs, pages 1--12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010."},{"key":"e_1_3_2_1_3_1","volume-title":"Streaming tree transducers. Journal of the ACM (JACM), 64(5):31","author":"Alur Rajeev","year":"2017","unstructured":"Rajeev Alur and Loris D'Antoni . Streaming tree transducers. Journal of the ACM (JACM), 64(5):31 , 2017 . Rajeev Alur and Loris D'Antoni. Streaming tree transducers. Journal of the ACM (JACM), 64(5):31, 2017."},{"key":"e_1_3_2_1_4_1","volume-title":"CSL-LICS 2014","author":"Alur Rajeev","year":"2014","unstructured":"Rajeev Alur , Adam Freilich , and Mukund Raghothaman . Regular combinators for string transformations. In Computer Science Logic and Logic in Computer Science , CSL-LICS 2014 , Vienna, Austria, pages 1--10. ACM , 2014 . Rajeev Alur, Adam Freilich, and Mukund Raghothaman. Regular combinators for string transformations. In Computer Science Logic and Logic in Computer Science, CSL-LICS 2014, Vienna, Austria, pages 1--10. ACM, 2014."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1614431.1614435"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1684"},{"issue":"4","key":"e_1_3_2_1_8_1","first-page":"3","article-title":"Some open problems in automata and logic","volume":"2","author":"Boja\u0144czyk Miko\u0142aj","year":"2014","unstructured":"Miko\u0142aj Boja\u0144czyk . Some open problems in automata and logic . ACM SIGLOG News , 2 ( 4 ): 3 -- 15 , 2014 . Miko\u0142aj Boja\u0144czyk. Some open problems in automata and logic. ACM SIGLOG News, 2(4):3--15, 2014.","journal-title":"ACM SIGLOG News"},{"key":"e_1_3_2_1_9_1","volume-title":"Recognisable languages over monads. CoRR, abs\/1502.04898","author":"Boja\u0144czyk Miko\u0142aj","year":"2015","unstructured":"Miko\u0142aj Boja\u0144czyk . Recognisable languages over monads. CoRR, abs\/1502.04898 , 2015 . Miko\u0142aj Boja\u0144czyk. Recognisable languages over monads. CoRR, abs\/1502.04898, 2015."},{"key":"e_1_3_2_1_10_1","volume-title":"LICS 2018","author":"Boja\u0144czyk Miko\u0142aj","year":"2018","unstructured":"Miko\u0142aj Boja\u0144czyk , Laure Daviaud , and Shankara Narayanan Krishna . Regular and First-Order List Functions. In Logic in Computer Science , LICS 2018 , Oxford, UK, pages 125--134. ACM , 2018 . Miko\u0142aj Boja\u0144czyk, Laure Daviaud, and Shankara Narayanan Krishna. Regular and First-Order List Functions. In Logic in Computer Science, LICS 2018, Oxford, UK, pages 125--134. ACM, 2018."},{"key":"e_1_3_2_1_11_1","volume-title":"First-order tree-to-tree functions. CoRR, abs\/2002.09307","author":"Boja\u0144czyk Miko\u0142aj","year":"2020","unstructured":"Miko\u0142aj Boja\u0144czyk and Amina Doumane . First-order tree-to-tree functions. CoRR, abs\/2002.09307 , 2020 . Miko\u0142aj Boja\u0144czyk and Amina Doumane. First-order tree-to-tree functions. CoRR, abs\/2002.09307, 2020."},{"key":"e_1_3_2_1_12_1","volume-title":"Wreath Products of Forest Algebras, with Applications to Tree Logics. Logical Methods in Computer Science, 8(3)","author":"Boja\u0144czyk Miko\u0142aj","year":"2012","unstructured":"Miko\u0142aj Boja\u0144czyk , Howard Straubing , and Igor Walukiewicz . Wreath Products of Forest Algebras, with Applications to Tree Logics. Logical Methods in Computer Science, 8(3) , 2012 . Miko\u0142aj Boja\u0144czyk, Howard Straubing, and Igor Walukiewicz. Wreath Products of Forest Algebras, with Applications to Tree Logics. Logical Methods in Computer Science, 8(3), 2012."},{"key":"e_1_3_2_1_13_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/3-540-08342-1_11","volume-title":"International Colloquium on Automata, Languages and Programming, ICALP, Turku, Finland","author":"Chytil Michal","year":"1977","unstructured":"Michal Chytil and Vojtech J\u00e1kl . Serial Composition of 2-Way Finite-State Transducers and Simple Programs on Strings . In International Colloquium on Automata, Languages and Programming, ICALP, Turku, Finland , volume 52 of Lecture Notes in Computer Science , pages 135 -- 147 . Springer , 1977 . Michal Chytil and Vojtech J\u00e1kl. Serial Composition of 2-Way Finite-State Transducers and Simple Programs on Strings. In International Colloquium on Automata, Languages and Programming, ICALP, Turku, Finland, volume 52 of Lecture Notes in Computer Science, pages 135--147. Springer, 1977."},{"key":"e_1_3_2_1_14_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1007\/978-3-540-73420-8_77","volume-title":"International Colloquium on Automata, Languages and Programming, ICALP, Wroc\u0142aw, Poland","author":"Colcombet Thomas","year":"2007","unstructured":"Thomas Colcombet . A Combinatorial Theorem for Trees . In International Colloquium on Automata, Languages and Programming, ICALP, Wroc\u0142aw, Poland , Lecture Notes in Computer Science , pages 901 -- 912 . Springer , 2007 . Thomas Colcombet. A Combinatorial Theorem for Trees. In International Colloquium on Automata, Languages and Programming, ICALP, Wroc\u0142aw, Poland, Lecture Notes in Computer Science, pages 901--912. Springer, 2007."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90387-H"},{"key":"e_1_3_2_1_16_1","volume-title":"LICS 2018","author":"Dave Vrunda","year":"2018","unstructured":"Vrunda Dave , Paul Gastin , and Shankara Narayanan Krishna . Regular transducer expressions for regular transformations. In Logic in Computer Science , LICS 2018 , Oxford, UK, pages 315--324 , 2018 . Vrunda Dave, Paul Gastin, and Shankara Narayanan Krishna. Regular transducer expressions for regular transformations. In Logic in Computer Science, LICS 2018, Oxford, UK, pages 315--324, 2018."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80041-1"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701394511"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/371316.371512"},{"key":"e_1_3_2_1_20_1","series-title":"LNCS","first-page":"195","volume-title":"FSTTCS","author":"\u00c9sik Z.","year":"2003","unstructured":"Z. \u00c9sik and P. Weil . On logically defined recognizable tree languages . In FSTTCS , volume 2914 of LNCS , pages 195 -- 207 , 2003 . Z. \u00c9sik and P. Weil. On logically defined recognizable tree languages. In FSTTCS, volume 2914 of LNCS, pages 195--207, 2003."},{"key":"e_1_3_2_1_21_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/978-3-662-49630-5_30","volume-title":"Foundations of Software Science and Computation Structures, FoSSaCS, Eindhoven, the Netherlands","author":"Fujii Soichiro","year":"2016","unstructured":"Soichiro Fujii , Shin-ya Katsumata, and Paul-Andr\u00e9 Melli\u00e8s . Towards a formal theory of graded monads . In Foundations of Software Science and Computation Structures, FoSSaCS, Eindhoven, the Netherlands , Lecture Notes in Computer Science , pages 513 -- 530 . Springer , 2016 . Soichiro Fujii, Shin-ya Katsumata, and Paul-Andr\u00e9 Melli\u00e8s. Towards a formal theory of graded monads. In Foundations of Software Science and Computation Structures, FoSSaCS, Eindhoven, the Netherlands, Lecture Notes in Computer Science, pages 513--530. Springer, 2016."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211035"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/3-540-18088-5_22","volume-title":"International Colloquium on Automata, Languages and Programming, ICALP, Turku, Finland","author":"Hafer Thilo","year":"1987","unstructured":"Thilo Hafer and Wolfgang Thomas . Computation tree logic CTL* and path quantifiers in the monadic theory of the binary tree . In International Colloquium on Automata, Languages and Programming, ICALP, Turku, Finland , pages 269 -- 279 . Springer , 1987 . Thilo Hafer and Wolfgang Thomas. Computation tree logic CTL* and path quantifiers in the monadic theory of the binary tree. In International Colloquium on Automata, Languages and Programming, ICALP, Turku, Finland, pages 269--279. Springer, 1987."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0188316-1"},{"key":"e_1_3_2_1_25_1","volume-title":"Counter-free automata","author":"McNaughton Robert","year":"1971","unstructured":"Robert McNaughton and Seymour Papert . Counter-free automata . The M.I.T. Press , Cambridge, Mass .-London, 1971 . Robert McNaughton and Seymour Papert. Counter-free automata. The M.I.T. Press, Cambridge, Mass.-London, 1971."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1080\/11663081.1992.10510780"},{"key":"e_1_3_2_1_27_1","volume-title":"Lectures on the Curry-Howard Isomorphism","author":"Sorensen Morten Heine","year":"2006","unstructured":"Morten Heine Sorensen and Pawel Urzyczyn . Lectures on the Curry-Howard Isomorphism . Elsevier , July 2006 . Morten Heine Sorensen and Pawel Urzyczyn. Lectures on the Curry-Howard Isomorphism. Elsevier, July 2006."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02485261"},{"key":"e_1_3_2_1_29_1","volume-title":"March","author":"Thatcher J. W.","year":"1968","unstructured":"J. W. Thatcher and J. B. Wright . Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical systems theory, 2(1):57--81 , March 1968 . J. W. Thatcher and J. B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical systems theory, 2(1):57--81, March 1968."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90090-3"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/267871.267878"}],"event":{"name":"LICS '20: 35th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society"],"location":"Saarbr\u00fccken Germany","acronym":"LICS '20"},"container-title":["Proceedings of the 35th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394785","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3373718.3394785","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:35Z","timestamp":1750197755000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,8]]},"references-count":30,"alternative-id":["10.1145\/3373718.3394785","10.1145\/3373718"],"URL":"https:\/\/doi.org\/10.1145\/3373718.3394785","relation":{},"subject":[],"published":{"date-parts":[[2020,7,8]]},"assertion":[{"value":"2020-07-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}