{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:15Z","timestamp":1750306335601,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":29,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,7,5]],"date-time":"2016-07-05T00:00:00Z","timestamp":1467676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-13- JS02-0010"],"award-info":[{"award-number":["ANR-13- JS02-0010"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"publisher","award":["CDR Project FLARE"],"award-info":[{"award-number":["CDR Project FLARE"]}],"id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"publisher"}]},{"name":"F\u00e9d\u00e9ration Wallonie-Bruxelles","award":["ARC Project TRANSFORM"],"award-info":[{"award-number":["ARC Project TRANSFORM"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,7,5]]},"DOI":"10.1145\/2933575.2934520","type":"proceedings-article","created":{"date-parts":[[2016,10,14]],"date-time":"2016-10-14T13:34:47Z","timestamp":1476452087000},"page":"387-396","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["First-order definability of rational transductions"],"prefix":"10.1145","author":[{"given":"Emmanuel","family":"Filiot","sequence":"first","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olivier","family":"Gauwin","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Bordeaux, LaBRI, CNRS"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Lhote","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Bordeaux, LaBRI, CNRS, Universit\u00e9 Libre de Bruxelles"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,7,5]]},"reference":[{"key":"e_1_3_2_1_1_1","series-title":"LIPIcs","first-page":"1","volume-title":"Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","author":"Alur R.","year":"2010","unstructured":"R. Alur and P. Cern\u00fd . Expressiveness of streaming string transducers . In Foundations of Software Technology and Theoretical Computer Science (FSTTCS) , volume 8 of LIPIcs , pages 1 -- 12 , 2010 . R. Alur and P. Cern\u00fd. Expressiveness of streaming string transducers. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 8 of LIPIcs, pages 1--12, 2010."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"e_1_3_2_1_3_1","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/978-3-662-43951-7_3","volume-title":"41st Internationl Colloquium on Automata, Languages, and Programming (ICALP)","author":"Bojanczyk M.","year":"2014","unstructured":"M. Bojanczyk . Transducers with origin information . In 41st Internationl Colloquium on Automata, Languages, and Programming (ICALP) , volume 8573 of LNCS , pages 26 -- 37 . Springer , 2014 . M. Bojanczyk. Transducers with origin information. In 41st Internationl Colloquium on Automata, Languages, and Programming (ICALP), volume 8573 of LNCS, pages 26--37. Springer, 2014."},{"key":"e_1_3_2_1_4_1","series-title":"LNCS","first-page":"141","volume-title":"Mathematical Foundations of Computer Science","author":"Cadilhac M.","year":"2015","unstructured":"M. Cadilhac , A. Krebs , M. Ludwig , and C. Paperman . A circuit complexity approach to transductions . In Mathematical Foundations of Computer Science , volume 9234 of LNCS , pages 141 -- 153 . Springer , 2015 . M. Cadilhac, A. Krebs, M. Ludwig, and C. Paperman. A circuit complexity approach to transductions. In Mathematical Foundations of Computer Science, volume 9234 of LNCS, pages 141--153. Springer, 2015."},{"key":"e_1_3_2_1_5_1","series-title":"LIPIcs","first-page":"160","volume-title":"Computer Science Logic (CSL)","author":"Carton O.","year":"2015","unstructured":"O. Carton and L. Dartois . Aperiodic two-way transducers and FO-transductions . In Computer Science Logic (CSL) , volume 41 of LIPIcs , pages 160 -- 174 , 2015 . O. Carton and L. Dartois. Aperiodic two-way transducers and FO-transductions. In Computer Science Logic (CSL), volume 41 of LIPIcs, pages 160--174, 2015."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90075-D"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00219-5"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90268-2"},{"key":"e_1_3_2_1_9_1","series-title":"Encyclopedia of mathematics and its applications","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach","author":"Courcelle B.","year":"2012","unstructured":"B. Courcelle and J. Engelfriet . Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach , volume 138 of Encyclopedia of mathematics and its applications . Cambridge University Press , 2012 . B. Courcelle and J. Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012."},{"key":"e_1_3_2_1_10_1","series-title":"Texts in Logic and Games","first-page":"261","volume-title":"Logic and Automata: History and Perspectives","author":"Diekert V.","year":"2008","unstructured":"V. Diekert and P. Gastin . First-order definable languages . In Logic and Automata: History and Perspectives , volume 2 of Texts in Logic and Games , pages 261 -- 306 . Amsterdam University Press , 2008 . V. Diekert and P. Gastin. First-order definable languages. In Logic and Automata: History and Perspectives, volume 2 of Texts in Logic and Games, pages 261--306. Amsterdam University Press, 2008."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9526-4"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054108005802"},{"key":"e_1_3_2_1_13_1","volume-title":"Finite model theory. Perspectives in Mathematical Logic","author":"Ebbinghaus H.","year":"1995","unstructured":"H. Ebbinghaus and J. Flum . Finite model theory. Perspectives in Mathematical Logic . Springer , 1995 . H. Ebbinghaus and J. Flum. Finite model theory. Perspectives in Mathematical Logic. Springer, 1995."},{"volume-title":"Automata, Languages, and Machines","author":"Eilenberg S.","key":"e_1_3_2_1_14_1","unstructured":"S. Eilenberg . Automata, Languages, and Machines . Volume A. Pure and Applied Mathematics. Academic press, 1974 . S. Eilenberg. Automata, Languages, and Machines. Volume A. Pure and Applied Mathematics. Academic press, 1974."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/371316.371512"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/978-3-662-45824-2_3","volume-title":"Logic and Its Applications (ICLA)","author":"Filiot E.","year":"2015","unstructured":"E. Filiot . Logic-automata connections for transformations . In Logic and Its Applications (ICLA) , pages 30 -- 57 . Springer , 2015 . E. Filiot. Logic-automata connections for transformations. In Logic and Its Applications (ICLA), pages 30--57. Springer, 2015."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2013.53"},{"key":"e_1_3_2_1_18_1","unstructured":"E.\n      Filiot S. N.\n      Krishna and \n      A.\n      Trivedi\n  . \n  First-order definable string transformations\n  . In Foundation of Software Technology and Theoretical Computer Science (FSTTCS) volume \n  29\n   of \n  LIPIcs pages \n  147\n  --\n  159 2014\n  .  E. Filiot S. N. Krishna and A. Trivedi. First-order definable string transformations. In Foundation of Software Technology and Theoretical Computer Science (FSTTCS) volume 29 of LIPIcs pages 147--159 2014."},{"key":"e_1_3_2_1_19_1","volume-title":"A note on finite-valued and finitely ambiguous transducers. Mathematical systems theory, 16(1):61--66","author":"Gurari E. M.","year":"1983","unstructured":"E. M. Gurari and O. H. Ibarra . A note on finite-valued and finitely ambiguous transducers. Mathematical systems theory, 16(1):61--66 , 1983 . E. M. Gurari and O. H. Ibarra. A note on finite-valued and finitely ambiguous transducers. Mathematical systems theory, 16(1):61--66, 1983."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764950"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.08.003"},{"key":"e_1_3_2_1_22_1","volume-title":"Counter-free automata","author":"McNaughton R.","year":"1971","unstructured":"R. McNaughton and S. Papert . Counter-free automata . M.I.T. Press , 1971 . R. McNaughton and S. Papert. Counter-free automata. M.I.T. Press, 1971."},{"issue":"1","key":"e_1_3_2_1_23_1","first-page":"239","article-title":"Some results on C-varieties","volume":"39","author":"Pin J.","year":"2005","unstructured":"J. Pin and H. Straubing . Some results on C-varieties . ITA , 39 ( 1 ): 239 -- 262 , 2005 . doi: 10.1051\/ita:2005014. 10.1051\/ita:2005014 J. Pin and H. Straubing. Some results on C-varieties. ITA, 39(1):239--262, 2005. doi: 10.1051\/ita:2005014.","journal-title":"ITA"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220042"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00180-Q"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1629683"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(61)80006-5"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90108-7"},{"key":"e_1_3_2_1_29_1","volume-title":"Formal Logic, and Circuit Complexity","author":"Straubing H.","year":"1994","unstructured":"H. Straubing . Finite Automata , Formal Logic, and Circuit Complexity . Birkh\u00e4user , Boston, Basel and Berlin, 1994 . H. Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Boston, Basel and Berlin, 1994."}],"event":{"name":"LICS '16: 31st 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":"New York NY USA","acronym":"LICS '16"},"container-title":["Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2933575.2934520","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2933575.2934520","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:53Z","timestamp":1750222493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2933575.2934520"}},"subtitle":["An algebraic approach"],"short-title":[],"issued":{"date-parts":[[2016,7,5]]},"references-count":29,"alternative-id":["10.1145\/2933575.2934520","10.1145\/2933575"],"URL":"https:\/\/doi.org\/10.1145\/2933575.2934520","relation":{},"subject":[],"published":{"date-parts":[[2016,7,5]]},"assertion":[{"value":"2016-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}