{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:23:34Z","timestamp":1770963814038,"version":"3.50.1"},"reference-count":31,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:p>We prove that for a given partial deterministic attributed tree transducer with monadic output, it is decidable whether or not an equivalent top-down tree transducer (with or without look-ahead) exists. We present a procedure that constructs such an equivalent top-down tree transducer (with or without look-ahead) if it exists. We then show that our results can be extended to arbitrary nondeterministic attributed tree transducer with look-around that have monadic output.<\/jats:p>","DOI":"10.1142\/s0129054125410059","type":"journal-article","created":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T02:57:36Z","timestamp":1745377056000},"page":"93-136","source":"Crossref","is-referenced-by-count":0,"title":["Deciding Whether an Attributed Translation can be Realized by a Top-Down Transducer"],"prefix":"10.1142","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8667-5436","authenticated-orcid":false,"given":"Sebastian","family":"Maneth","sequence":"first","affiliation":[{"name":"FB3 \u2014 Informatik, Universit\u00e4t Bremen, Bibliothekstrasse 5, Bremen, Bremen, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3581-7227","authenticated-orcid":false,"given":"Martin","family":"Vu","sequence":"additional","affiliation":[{"name":"FB3 \u2014 Informatik, Universit\u00e4t Bremen, Bibliothekstrasse 5, Bremen, Bremen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2025,4,22]]},"reference":[{"key":"S0129054125410059BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(79)90561-8"},{"issue":"4","key":"S0129054125410059BIB002","volume":"14","author":"Baschenis F.","year":"2018","journal-title":"Log. Methods Comput. Sci."},{"key":"S0129054125410059BIB003","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1684"},{"key":"S0129054125410059BIB004","volume-title":"Tree Automata Techniques and Applications","author":"Comon H.","year":"2008"},{"key":"S0129054125410059BIB005","volume-title":"Grammatical Picture Generation \u2014 A Tree-Based Approach","author":"Drewes F.","year":"2006"},{"key":"S0129054125410059BIB006","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2715"},{"key":"S0129054125410059BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683280"},{"key":"S0129054125410059BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90060-1"},{"key":"S0129054125410059BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-019-00360-8"},{"key":"S0129054125410059BIB010","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2807"},{"key":"S0129054125410059BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-003-0120-0"},{"key":"S0129054125410059BIB012","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701394511"},{"key":"S0129054125410059BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.05.015"},{"key":"S0129054125410059BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90066-2"},{"key":"S0129054125410059BIB015","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2013.53"},{"key":"S0129054125410059BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.011"},{"issue":"3","key":"S0129054125410059BIB017","first-page":"261","volume":"5","author":"F\u00fcl\u00f6p Z.","year":"1981","journal-title":"Acta Cybern."},{"key":"S0129054125410059BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00028-4"},{"key":"S0129054125410059BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-72248-6"},{"key":"S0129054125410059BIB020","unstructured":"P. Gallot, S. Maneth, K. Nakano and C. Peyrat, Deciding linear height and linear size-to-height increase for macro tree transducers (2024)."},{"key":"S0129054125410059BIB021","volume-title":"Tree Automata","author":"G\u00e9cseg F.","year":"1984"},{"key":"S0129054125410059BIB022","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816714"},{"key":"S0129054125410059BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/BF01692511"},{"key":"S0129054125410059BIB024","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.08.003"},{"key":"S0129054125410059BIB025","series-title":"LIPIcs","first-page":"134:1","volume-title":"ICALP","volume":"168","author":"Maneth S.","year":"2020"},{"key":"S0129054125410059BIB026","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-40247-0_17"},{"key":"S0129054125410059BIB027","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-71112-1_16"},{"key":"S0129054125410059BIB028","doi-asserted-by":"publisher","DOI":"10.1007\/BF01695769"},{"key":"S0129054125410059BIB029","unstructured":"J. Schmude, Equivalence problem of transductions: algorithms based on commutative algebra, phd thesis, University of Warsaw (2021)."},{"key":"S0129054125410059BIB030","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjtrans.7.82"},{"key":"S0129054125410059BIB031","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80017-4"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054125410059","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T05:37:19Z","timestamp":1770961039000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054125410059"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,22]]},"references-count":31,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["10.1142\/S0129054125410059"],"URL":"https:\/\/doi.org\/10.1142\/s0129054125410059","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,22]]}}}