Relating tree series transducers and weighted tree automata

Bottom-up tree series transducers (tst) over the semiring A are implemented with the help of bottom-up weighted tree automata (wta) over an extension of A. Therefore bottom-up D-weighted tree automata (D-wta) with D a distributive Q-algebra are introduced. A D-wta is essentially a wta but uses as transition weight an operation symbol of the Omega-algebra D instead of a semiring element. The given tst is implemented with the help of a D-wta, essentially showing that D-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 D-wta. The applicability of the obtained presentation result is demonstrated by deriving a pumping lemma for deterministic finite D-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 D-wta. Thus with help of a weaker version of the derived pumping lemma, decidability of the emptiness problem for finite D-wta is shown under mild conditions on D.