Semirings and Tree-to-Graph-to-Tree Transductions
Frank Drewes · Electronic Notes in Theoretical Computer Science · 1995
It is shown that top-down tree transducers are as powerful as sharing-free tree-to-graph-to-tree transducers as far as the computation of functions is considered whose codomain is a semiring. I am grateful to Renate Klempien-Hinrichs and to the referees, who gave helpful hints on the presentation of the work reported here.