{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T04:18:42Z","timestamp":1749010722441,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531310"},{"type":"electronic","value":"9783662531327"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53132-7_29","type":"book-chapter","created":{"date-parts":[[2016,7,20]],"date-time":"2016-07-20T01:25:06Z","timestamp":1468977906000},"page":"355-367","source":"Crossref","is-referenced-by-count":2,"title":["Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Adrien","family":"Boiret","sequence":"first","affiliation":[]},{"given":"Raphaela","family":"Palenta","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,7,21]]},"reference":[{"key":"29_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/978-3-319-30000-9_34","volume-title":"Language and Automata Theory and Applications","author":"A Boiret","year":"2016","unstructured":"Boiret, A.: Normal form on linear tree-to-word transducers. In: Dediu, A.-H., et al. (eds.) Language and Automata Theory and Applications. LNCS, vol. 9618, pp. 439\u2013451. Springer, Heidelberg (2016)"},{"key":"29_CR2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/B978-0-12-115350-2.50014-2","volume-title":"Formal Language Theory, Perspectives and Open Problems","author":"J Engelfriet","year":"1980","unstructured":"Engelfriet, J.: Some open question and recent results on tree transducers and tree languages. In: Book, R.V. (ed.) Formal Language Theory, Perspectives and Open Problems, pp. 241\u2013286. Academic Press, New York (1980)"},{"issue":"4","key":"29_CR3","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1137\/S0097539701394511","volume":"32","author":"J Engelfriet","year":"2003","unstructured":"Engelfriet, J., Maneth, S.: Macro tree translations of linear size increase are MSO definable. SIAM J. Comput. 32(4), 950\u20131006 (2003)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"29_CR4","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.ipl.2006.05.015","volume":"100","author":"J Engelfriet","year":"2006","unstructured":"Engelfriet, J., Maneth, S.: The equivalence problem for deterministic MSO tree transducers is decidable. Inf. Process. Lett. 100(5), 206\u2013212 (2006)","journal-title":"Inf. Process. Lett."},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Engelfriet, J., Rozenberg, G., Slutzki, G.: Tree transducers, L systems and two-way machines. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 66\u201374. ACM (1978)","DOI":"10.1145\/800133.804333"},{"issue":"1","key":"29_CR6","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0022-0000(85)90066-2","volume":"31","author":"J Engelfriet","year":"1985","unstructured":"Engelfriet, J., Vogler, H.: Macro tree transducers. J. Comput. Syst. Sci. 31(1), 71\u2013146 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"29_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/978-3-642-21254-3_28","volume-title":"Language and Automata Theory and Applications","author":"G Laurence","year":"2011","unstructured":"Laurence, G., Lemay, A., Niehren, J., Staworko, S., Tommasi, M.: Normalization of sequential top-down tree-to-word transducers. In: Dediu, A.-H., Inenaga, S., Mart\u00edn-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 354\u2013365. Springer, Heidelberg (2011)"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Lemay, A., Maneth, S., Niehren, J.: A learning algorithm for top-down XML transformations. In: Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 285\u2013296 (2010)","DOI":"10.1145\/1807085.1807122"},{"key":"29_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4939-0748-9","volume-title":"The Compressed Word Problem for Groups","author":"M Lohrey","year":"2014","unstructured":"Lohrey, M.: The Compressed Word Problem for Groups. Springer, New York (2014)"},{"key":"29_CR10","unstructured":"Maneth, S., Seidl, H.: Deciding equivalence of top-down XML transformations in polynomial time. In: Programming Language Technologies for XML, pp. 73\u201379 (2007)"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: The complexity of the morphism equivalence problem for context-free languages. Ph.D. thesis, Warsaw University (1995)","DOI":"10.1007\/BFb0049431"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"Seidl, H., Maneth, S., Kemper, G.: Equivalence of deterministic top-down tree-to-string transducers is decidable. In: IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 943\u2013962 (2015)","DOI":"10.1109\/FOCS.2015.62"},{"key":"29_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1007\/978-3-642-03409-1_28","volume-title":"Fundamentals of Computation Theory","author":"S Staworko","year":"2009","unstructured":"Staworko, S., Laurence, G., Lemay, A., Niehren, J.: Equivalence of deterministic nested word to word transducers. In: Charatonik, W., G\u0119bala, M., Kuty\u0142owski, M. (eds.) FCT 2009. LNCS, vol. 5699, pp. 310\u2013322. Springer, Heidelberg (2009)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53132-7_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T02:17:15Z","timestamp":1749003435000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53132-7_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531310","9783662531327"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53132-7_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}