{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:34Z","timestamp":1760202514715},"reference-count":19,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,8]]},"abstract":"<jats:p> Bottom-up tree series transducers (tst) over the semiring [Formula: see text] are implemented with the help of bottom-up weighted tree automata (wta) over an extension of [Formula: see text]. Therefore bottom-up [Formula: see text]-weighted tree automata ([Formula: see text]-wta) with [Formula: see text] a distributive \u03a9-algebra are introduced. A [Formula: see text]-wta is essentially a wta but uses as transition weight an operation symbol of the \u03a9-algebra [Formula: see text] instead of a semiring element. The given tst is implemented with the help of a [Formula: see text]-wta, essentially showing that [Formula: see text]-wta are a joint generalization of tst (using IO-substitution) and wta. Then a semiring and a wta are constructed such that the wta computes a formal representation of the semantics of the [Formula: see text]-wta. The applicability of the obtained presentation result is demonstrated by deriving a pumping lemma for deterministic finite [Formula: see text]-wta from a known pumping lemma for deterministic finite wta. Finally, it is observed that the known decidability results for emptiness cannot be applied to obtain decidability of emptiness for finite [Formula: see text]-wta. Thus with help of a weaker version of the derived pumping lemma, decidability of the emptiness problem for finite [Formula: see text]-wta is shown under mild conditions on [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s012905410500325x","type":"journal-article","created":{"date-parts":[[2005,7,5]],"date-time":"2005-07-05T14:52:13Z","timestamp":1120575133000},"page":"723-741","source":"Crossref","is-referenced-by-count":11,"title":["RELATING TREE SERIES TRANSDUCERS AND WEIGHTED TREE AUTOMATA"],"prefix":"10.1142","volume":"16","author":[{"given":"ANDREAS","family":"MALETTI","sequence":"first","affiliation":[{"name":"Fakult\u00e4t Informatik, Technische  Universit\u00e4t Dresden, D\u201301062 Dresden, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90019-6"},{"key":"rf3","first-page":"509","volume":"16","author":"Borchardt B.","journal-title":"Acta Cybernet."},{"key":"rf4","first-page":"417","volume":"8","author":"Borchardt B.","journal-title":"J. Autom. Lang. Comb."},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000110"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.2890"},{"key":"rf7","unstructured":"S.\u00a0Bozapalidis and G.\u00a0Rahonis, Weighted Automata: Theory and Applications, eds. M.\u00a0Droste and H.\u00a0Vogler (Technische Universit\u00e4t Dresden, 2004)\u00a0p. 34."},{"key":"rf9","series-title":"Pure and Applied Mathematics","volume-title":"Automata, Languages, and Machines\u2014Volume A","volume":"59","author":"Eilenberg S.","year":"1974"},{"key":"rf10","first-page":"11","volume":"7","author":"Engelfriet J.","journal-title":"J. Autom. Lang. Comb."},{"key":"rf11","first-page":"219","volume":"8","author":"\u00c9sik Z.","journal-title":"J. Autom. Lang. Comb."},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1072-z"},{"key":"rf13","volume-title":"Tree Automata","author":"G\u00e9cseg F.","year":"1984"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6_1"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321997"},{"key":"rf17","first-page":"135","volume":"14","author":"Kuich W.","journal-title":"Acta Cybernet."},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69959-7"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01695769"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6"},{"key":"rf23","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\/S012905410500325X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:38:42Z","timestamp":1565138322000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905410500325X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,8]]},"references-count":19,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,8]]}},"alternative-id":["10.1142\/S012905410500325X"],"URL":"https:\/\/doi.org\/10.1142\/s012905410500325x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,8]]}}}