{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:21Z","timestamp":1740133941191,"version":"3.37.3"},"reference-count":31,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["1763"],"award-info":[{"award-number":["1763"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:p> Conjecture 11 of [Lagoutte, Maletti: Survey \u2014 Weighted extended top-down tree transducers \u2014 Part III: Composition. Proc. AFCS, LNCS 7020, p. 272\u2013308, Springer 2011] is confirmed. It is demonstrated that the composition of a constant weighted extended tree transducer with a linear weighted top-down tree transducer can be computed by a single weighted extended tree transducer. Whereas linearity and the top-down property are syntactic, the constant property is semantic. The decidability of the constant property is investigated in several restricted settings. <\/jats:p>","DOI":"10.1142\/s0129054122450010","type":"journal-article","created":{"date-parts":[[2022,11,9]],"date-time":"2022-11-09T16:27:02Z","timestamp":1668011222000},"page":"539-558","source":"Crossref","is-referenced-by-count":1,"title":["Compositions with Constant Weighted Extended Tree Transducers"],"prefix":"10.1142","volume":"34","author":[{"given":"Malte","family":"Blattmann","sequence":"first","affiliation":[{"name":"Universit\u00e4t Leipzig, Faculty of Mathematics and Computer Science, PO Box 100 920, 04009 Leipzig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3202-0498","authenticated-orcid":false,"given":"Andreas","family":"Maletti","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Leipzig, Faculty of Mathematics and Computer Science, PO Box 100 920, 04009 Leipzig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,11,9]]},"reference":[{"key":"S0129054122450010BIB001","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/978-3-540-76336-9_3","volume-title":"Proc. 12th Int. Conf. Implementation and Application of Automata","volume":"4783","author":"Allauzen C.","year":"2007"},{"issue":"4","key":"S0129054122450010BIB002","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0304-3975(82)90098-6","volume":"20","author":"Arnold A.","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"S0129054122450010BIB003","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1007\/978-3-030-81508-0_6","volume-title":"Proc. 25th Int. Conf. Developments in Language Theory","volume":"12811","author":"Blattmann M.","year":"2021"},{"issue":"1","key":"S0129054122450010BIB005","doi-asserted-by":"crossref","first-page":"37","DOI":"10.3233\/FI-2015-1143","volume":"136","author":"Droste M.","year":"2015","journal-title":"Fundamenta Informaticae"},{"issue":"1","key":"S0129054122450010BIB006","first-page":"11","volume":"7","author":"Engelfriet J.","year":"2002","journal-title":"J. Automata, Languages and Combinatorics"},{"issue":"1","key":"S0129054122450010BIB007","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/BF01683280","volume":"10","author":"Engelfriet J.","year":"1977","journal-title":"Math. Syst. Th."},{"issue":"2","key":"S0129054122450010BIB008","doi-asserted-by":"crossref","first-page":"163","DOI":"10.3233\/FI-2011-559","volume":"111","author":"F\u00fcl\u00f6p Z.","year":"2011","journal-title":"Fundamenta Informaticae"},{"key":"S0129054122450010BIB009","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/978-3-030-23679-3_11","volume-title":"Proc. 24th Int. Conf. Implementation and Application of Automata","volume":"11601","author":"F\u00fcl\u00f6p Z.","year":"2019"},{"key":"S0129054122450010BIB010","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-72248-6","volume-title":"Syntax-Directed Semantics \u2014 Formal Models Based on Tree Transducers","author":"F\u00fcl\u00f6p Z.","year":"1998"},{"issue":"3","key":"S0129054122450010BIB011","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s00224-003-1072-z","volume":"36","author":"F\u00fcl\u00f6p Z.","year":"2003","journal-title":"Theory of Computing Systems"},{"key":"S0129054122450010BIB012","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/978-3-642-01492-5_9","volume-title":"Handbook of Weighted Automata","author":"F\u00fcl\u00f6p Z.","year":"2009"},{"key":"S0129054122450010BIB013","volume-title":"Tree Automata","author":"G\u00e9cseg F.","year":"1984","edition":"2"},{"key":"S0129054122450010BIB014","first-page":"1","volume-title":"Handbook of Formal Languages","author":"G\u00e9cseg F.","year":"1997"},{"key":"S0129054122450010BIB015","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-015-9333-5","volume-title":"Semirings and Their Applications","author":"Golan J. S.","year":"1999"},{"issue":"3","key":"S0129054122450010BIB016","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1162\/coli.2008.07-051-R2-03-57","volume":"34","author":"Graehl J.","year":"2008","journal-title":"Computational Linguistics"},{"issue":"1","key":"S0129054122450010BIB017","first-page":"1","volume":"14","author":"Hanneforth T.","year":"2018","journal-title":"Logical Methods in Computer Science"},{"key":"S0129054122450010BIB018","doi-asserted-by":"publisher","DOI":"10.1142\/3903"},{"issue":"2","key":"S0129054122450010BIB019","doi-asserted-by":"crossref","first-page":"211","DOI":"10.14232\/actacyb.20.2.2011.1","volume":"20","author":"Kirsten D.","year":"2011","journal-title":"Acta Cybernetica"},{"key":"S0129054122450010BIB020","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-540-30586-6_1","volume-title":"Proc. 6th Int. Conf. Intelligent Text Processing and Computational Linguistics","volume":"3406","author":"Knight K.","year":"2005"},{"volume-title":"Statistical Machine Translation","year":"2010","author":"Koehn P.","key":"S0129054122450010BIB021"},{"issue":"1","key":"S0129054122450010BIB022","first-page":"135","volume":"14","author":"Kuich W.","year":"1999","journal-title":"Acta Cybernetica"},{"key":"S0129054122450010BIB023","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1007\/978-3-642-24897-9_13","volume-title":"Proc. Workshop Algebraic Foundations in Computer Science","volume":"7020","author":"Lagoutte A.","year":"2011"},{"issue":"2","key":"S0129054122450010BIB024","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/070699160","volume":"39","author":"Maletti A.","year":"2009","journal-title":"SIAM J. Comput."},{"issue":"9","key":"S0129054122450010BIB025","doi-asserted-by":"crossref","first-page":"1187","DOI":"10.1016\/j.ic.2008.03.019","volume":"206","author":"Maletti A.","year":"2008","journal-title":"Inform. Comput."},{"key":"S0129054122450010BIB026","first-page":"1058","volume-title":"Proc. 48th Ann. Meeting Association for Computational Linguistics","author":"May J.","year":"2010"},{"issue":"1","key":"S0129054122450010BIB027","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1006\/csla.2001.0184","volume":"16","author":"Mohri M.","year":"2002","journal-title":"Computer Speech & Language"},{"issue":"3","key":"S0129054122450010BIB028","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF01695769","volume":"4","author":"Rounds W. C.","year":"1970","journal-title":"Math. Syst. Th."},{"issue":"4","key":"S0129054122450010BIB029","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/S0022-0000(70)80017-4","volume":"4","author":"Thatcher J. W.","year":"1970","journal-title":"J. Comput. Syst. Sci."},{"key":"S0129054122450010BIB030","first-page":"143","volume-title":"Currents in the Theory of Computing","author":"Thatcher J. W.","year":"1973"},{"issue":"3","key":"S0129054122450010BIB031","first-page":"391","volume":"23","author":"Wang H.","year":"1997","journal-title":"Houston Journal of Mathematics"},{"key":"S0129054122450010BIB032","first-page":"303","volume-title":"Proc. 40th Ann. Meeting Association for Computational Linguistics","author":"Yamada K.","year":"2002"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122450010","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T08:11:50Z","timestamp":1695456710000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054122450010"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,9]]},"references-count":31,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["10.1142\/S0129054122450010"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122450010","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2022,11,9]]}}}