{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:12:13Z","timestamp":1767237133216,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2017,8,29]],"date-time":"2017-08-29T00:00:00Z","timestamp":1503964800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF Expeditions in Computing","award":["CCF 1138996"],"award-info":[{"award-number":["CCF 1138996"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>\n            The theory of tree transducers provides a foundation for understanding expressiveness and complexity of analysis problems for specification languages for transforming hierarchically structured data such as XML documents. We introduce\n            <jats:italic>streaming tree transducers<\/jats:italic>\n            as an analyzable, executable, and expressive model for transforming unranked ordered trees (and forests) in a single pass. Given a linear encoding of the input tree, the transducer makes a single left-to-right pass through the input, and computes the output in linear time using a finite-state control, a visibly pushdown stack, and a finite number of variables that store output chunks that can be combined using the operations of string-concatenation and tree-insertion. We prove that the expressiveness of the model coincides with transductions definable using monadic second-order logic (MSO). Existing models of tree transducers either cannot implement all MSO-definable transformations, or require\n            <jats:italic>regular look-ahead<\/jats:italic>\n            that prohibits single-pass implementation. We show a variety of analysis problems such as\n            <jats:italic>type-checking<\/jats:italic>\n            and checking\n            <jats:italic>functional equivalence<\/jats:italic>\n            are decidable for our model.\n          <\/jats:p>","DOI":"10.1145\/3092842","type":"journal-article","created":{"date-parts":[[2017,8,29]],"date-time":"2017-08-29T17:49:18Z","timestamp":1504028958000},"page":"1-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Streaming Tree Transducers"],"prefix":"10.1145","volume":"64","author":[{"given":"Rajeev","family":"Alur","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}]},{"given":"Loris","family":"D'antoni","sequence":"additional","affiliation":[{"name":"University of Wisconsin\u2013Madison, Madison, USA"}]}],"member":"320","published-online":{"date-parts":[[2017,8,29]]},"reference":[{"volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (LIPIcs 8). 1--12","author":"Alur R.","key":"e_1_2_1_1_1","unstructured":"R. Alur and P. Cern\u00fd . 2010. Expressiveness of streaming string transducers . In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (LIPIcs 8). 1--12 . R. Alur and P. Cern\u00fd. 2010. Expressiveness of streaming string transducers. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (LIPIcs 8). 1--12."},{"volume-title":"Proceedings of the 38th ACM Symposium on Principles of Programming Languages (POPL\u201911)","author":"Alur R.","key":"e_1_2_1_2_1","unstructured":"R. Alur and P. Cern\u00fd . 2011. Streaming transducers for algorithmic verification of single-pass list-processing programs . In Proceedings of the 38th ACM Symposium on Principles of Programming Languages (POPL\u201911) . 599--610. R. Alur and P. Cern\u00fd. 2011. Streaming transducers for algorithmic verification of single-pass list-processing programs. In Proceedings of the 38th ACM Symposium on Principles of Programming Languages (POPL\u201911). 599--610."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516518"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1684"},{"key":"e_1_2_1_5_1","unstructured":"H. Comon M. Dauchet R. Gilleron D. Lugiez S. Tison and M. Tommasi. 2002. Tree automata techniques and applications. Retrieved from http:\/\/www.grappa.univ-lille3.fr\/tata\/.  H. Comon M. Dauchet R. Gilleron D. Lugiez S. Tison and M. Tommasi. 2002. Tree automata techniques and applications. Retrieved from http:\/\/www.grappa.univ-lille3.fr\/tata\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90268-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_14"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2791292"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01704020"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/371316.371512"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85780-8_23"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2807"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1816"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.05.015"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.01.001"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90066-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/263139.263146"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Supratik Chakraborty and Amit Kumar (Eds.)","volume":"13","author":"Filiot E.","unstructured":"E. Filiot , O. Gauwin , P. Reynier , and F. Servais . 2011. Streamability of nested word transductions .. In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Supratik Chakraborty and Amit Kumar (Eds.) , Vol. 13 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 312--324. E. Filiot, O. Gauwin, P. Reynier, and F. Servais. 2011. Streamability of nested word transductions.. In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Supratik Chakraborty and Amit Kumar (Eds.), Vol. 13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 312--324."},{"key":"e_1_2_1_19_1","volume-title":"On streaming string transducers and HDT0L systems. CoRR abs\/1412.0537","author":"Filiot E.","year":"2014","unstructured":"E. Filiot and Pierre-Alain Reynier . 2014. On streaming string transducers and HDT0L systems. CoRR abs\/1412.0537 ( 2014 ). http:\/\/arxiv.org\/abs\/1412.0537 E. Filiot and Pierre-Alain Reynier. 2014. On streaming string transducers and HDT0L systems. CoRR abs\/1412.0537 (2014). http:\/\/arxiv.org\/abs\/1412.0537"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816714"},{"volume-title":"Foundations of XML Processing: The Tree-Automata Approach","author":"Hosoya H.","key":"e_1_2_1_21_1","unstructured":"H. Hosoya . 2011. Foundations of XML Processing: The Tree-Automata Approach . Cambridge University Press . H. Hosoya. 2011. Foundations of XML Processing: The Tree-Automata Approach. Cambridge University Press."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/767193.767195"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.21"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80045-0"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03816-7_48"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36206-1_24"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054115400134"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.035"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335171"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/982962.964029"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00301-2"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.05.001"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_32"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543622"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_94"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/359997.359999"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3092842","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3092842","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:37:28Z","timestamp":1750217848000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3092842"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,29]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3092842"],"URL":"https:\/\/doi.org\/10.1145\/3092842","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2017,8,29]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}