{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:36:39Z","timestamp":1758274599981,"version":"3.44.0"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030171261"},{"type":"electronic","value":"9783030171278"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"vor","delay-in-days":94,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In 1982, Courcelle and Franchi-Zannettacci showed that the equivalence problem of separated non-nested attribute systems can be reduced to the equivalence problem of total deterministic separated basic macro tree transducers. They also gave a procedure for deciding equivalence of transducer in the latter class. Here, we reconsider this equivalence problem. We present a new alternative decision procedure and prove that it runs in polynomial time. We also consider extensions of this result to partial transducers and to the case where parameters of transducers accumulate strings instead of trees.<\/jats:p>","DOI":"10.1007\/978-3-030-17127-8_28","type":"book-chapter","created":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T11:11:46Z","timestamp":1554462706000},"page":"488-504","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Deciding Equivalence of Separated Non-nested Attribute Systems in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Helmut","family":"Seidl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raphaela","family":"Palenta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Maneth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,5]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Alur, R., D\u2019Antoni, L.: Streaming tree transducers. J. ACM 64(5):31:1\u201331:55 (2017)","DOI":"10.1145\/3092842"},{"key":"28_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-662-43951-7_3","volume-title":"Automata, Languages, and Programming","author":"M Boja\u0144czyk","year":"2014","unstructured":"Boja\u0144czyk, M.: Transducers with origin information. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 26\u201337. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_3"},{"issue":"2","key":"28_CR3","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0304-3975(82)90003-2","volume":"17","author":"B Courcelle","year":"1982","unstructured":"Courcelle, B., Franchi-Zannettacci, P.: Attribute grammars and recursive program schemes I. Theor. Comput. Sci. 17(2), 163\u2013191 (1982)","journal-title":"Theor. Comput. Sci."},{"key":"28_CR4","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/BF01683280","volume":"10","author":"J Engelfriet","year":"1977","unstructured":"Engelfriet, J.: Top-down tree transducers with regular look-ahead. Math. Syst. Theory 10, 289\u2013303 (1977)","journal-title":"Math. Syst. Theory"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Engelfriet, J.: Some open questions and recent results on tree transducers and tree languages. In: Formal Language Theory, pp. 241\u2013286. Elsevier (1980)","DOI":"10.1016\/B978-0-12-115350-2.50014-2"},{"issue":"4","key":"28_CR6","doi-asserted-by":"publisher","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":"28_CR7","doi-asserted-by":"publisher","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."},{"issue":"5","key":"28_CR8","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/j.jcss.2009.01.001","volume":"75","author":"J Engelfriet","year":"2009","unstructured":"Engelfriet, J., Maneth, S., Seidl, H.: Deciding equivalence of top-down XML transformations in polynomial time. J. Comput. Syst. Sci. 75(5), 271\u2013286 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"28_CR9","doi-asserted-by":"publisher","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."},{"issue":"1","key":"28_CR10","first-page":"1","volume":"5","author":"Z \u00c9sik","year":"1980","unstructured":"\u00c9sik, Z.: Decidability results concerning tree transducers I. Acta Cybern. 5(1), 1\u201320 (1980)","journal-title":"Acta Cybern."},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"Filiot, E., Maneth, S., Reynier, P., Talbot, J.: Decision problems of tree transducers with origin. Inf. Comput. 261(Part), 311\u2013335 (2018)","DOI":"10.1016\/j.ic.2018.02.011"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"Fors, N., Cedersj\u00f6, G., Hedin, G.: JavaRAG: a Java library for reference attribute grammars. In: Proceedings of the 14th International Conference on Modularity, MODULARITY 2015, pp. 55\u201367. ACM, New York (2015)","DOI":"10.1145\/2724525.2724572"},{"issue":"7","key":"28_CR13","doi-asserted-by":"publisher","first-page":"1607","DOI":"10.1142\/S012905411100891X","volume":"22","author":"S Friese","year":"2011","unstructured":"Friese, S., Seidl, H., Maneth, S.: Earliest normal form and minimization for bottom-up tree transducers. Int. J. Found. Comput. Sci. 22(7), 1607\u20131623 (2011)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3","key":"28_CR14","first-page":"261","volume":"5","author":"Z F\u00fcl\u00f6p","year":"1981","unstructured":"F\u00fcl\u00f6p, Z.: On attributed tree transducers. Acta Cybern. 5(3), 261\u2013279 (1981)","journal-title":"Acta Cybern."},{"key":"28_CR15","series-title":"Monographs in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-72248-6","volume-title":"Syntax-Directed Semantics - Formal Models Based on Tree Transducers","author":"Z F\u00fcl\u00f6p","year":"1998","unstructured":"F\u00fcl\u00f6p, Z., Vogler, H.: Syntax-Directed Semantics - Formal Models Based on Tree Transducers. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/978-3-642-72248-6"},{"issue":"1","key":"28_CR16","first-page":"37","volume":"4","author":"F G\u00e9cseg","year":"1978","unstructured":"G\u00e9cseg, F., Steinby, M.: Minimal ascending tree automata. Acta Cybern. 4(1), 37\u201344 (1978)","journal-title":"Acta Cybern."},{"key":"28_CR17","volume-title":"Tree Automata","author":"F G\u00e9cseg","year":"1984","unstructured":"G\u00e9cseg, F., Steinby, M.: Tree Automata. Akad\u00e9niai Kiad\u00f3, Budapest (1984)"},{"issue":"3","key":"28_CR18","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1145\/321466.321473","volume":"15","author":"TV Griffiths","year":"1968","unstructured":"Griffiths, T.V.: The unsolvability of the equivalence problem for lambda-free nondeterministic generalized machines. J. ACM 15(3), 409\u2013413 (1968)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"28_CR19","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/S0304-3975(00)00158-4","volume":"244","author":"J Honkala","year":"2000","unstructured":"Honkala, J.: A short solution for the HDT0L sequence equivalence problem. Theor. Comput. Sci. 244(1\u20132), 267\u2013270 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"28_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01692511","volume":"2","author":"DE Knuth","year":"1968","unstructured":"Knuth, D.E.: Semantics of context-free languages. Math. Syst. Theory 2(2), 127\u2013145 (1968)","journal-title":"Math. Syst. Theory"},{"issue":"1","key":"28_CR21","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF01702865","volume":"5","author":"DE Knuth","year":"1971","unstructured":"Knuth, D.E.: Correction: semantics of context-free languages. Math. Syst. Theory 5(1), 95\u201396 (1971)","journal-title":"Math. Syst. Theory"},{"key":"28_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1007\/978-3-642-21254-3_28"},{"key":"28_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019","volume-title":"Algebraic Combinatorics on Words","author":"M Lothaire","year":"2002","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002)"},{"issue":"2","key":"28_CR24","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1070\/SM1977v032n02ABEH002376","volume":"32","author":"GS Makanin","year":"1977","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Math. USSR-Sb. 32(2), 129 (1977)","journal-title":"Math. USSR-Sb."},{"issue":"8","key":"28_CR25","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1142\/S0129054115400134","volume":"26","author":"S Maneth","year":"2015","unstructured":"Maneth, S.: A survey on decidable equivalence problems for tree transducers. Int. J. Found. Comput. Sci. 26(8), 1069\u20131100 (2015)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"28_CR26","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in PSPACE. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, 17\u201318 October 1999, pp. 495\u2013500. IEEE Computer Society (1999)","DOI":"10.1109\/SFFCS.1999.814622"},{"key":"28_CR27","doi-asserted-by":"crossref","unstructured":"Seidl, H., Maneth, S., Kemper, G.: Equivalence of deterministic top-down tree-to-string transducers is decidable. J. ACM 65(4), 21:1\u201321:30 (2018)","DOI":"10.1145\/3182653"},{"key":"28_CR28","doi-asserted-by":"crossref","unstructured":"Sloane, A.M., Kats, L.C., Visser, E.: A pure embedding of attribute grammars. Sci. Comput. Program. 78(10), 1752\u20131769 (2013). Special Section on Language Descriptions Tools and Applications (LDTA 2008 and 2009) & Special Section on Software Engineering Aspects of Ubiquitous Computing and Ambient Intelligence (UCAm I 2011)","DOI":"10.1016\/j.scico.2011.11.005"},{"issue":"1\u20132","key":"28_CR29","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.scico.2009.07.004","volume":"75","author":"E Van Wyk","year":"2010","unstructured":"Van Wyk, E., Bodin, D., Gao, J., Krishnan, L.: Silver: an extensible attribute grammar system. Sci. Comput. Program. 75(1\u20132), 39\u201354 (2010)","journal-title":"Sci. Comput. Program."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17127-8_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T18:00:00Z","timestamp":1757095200000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17127-8_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030171261","9783030171278"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17127-8_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"5 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 April 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2019\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}