Bottom-Up and Top-Down Tree Series Transformations
Joost Engelfriet, Zoltán Fülöp, Heiko Vogler · Journal of automata, languages and combinatorics · 2002
We generalize bottom-up tree transducers and top-down tree transducers to the concept of bottom-up tree series transducer and top-down tree series transducer, respectively, by allowing formal tree series as output rather than trees, where a formal tree series is a mapping from output trees to some semiring. We associate two semantics with a tree series transducer: a mapping which transforms trees into tree series (for short: tree to tree series transformation or t-ts transformation), and a mapping which transforms tree series into tree series (for short: tree series transformation or ts-ts transformation). We show that the standard case of tree transducers is reobtained by choosing the boolean semiring under the t-ts semantics. Moreover, we show that certain fundamental constructions and results concerning bottom-up and top-down tree transducers can be generalized for the corresponding tree series transducers. Among others, we prove that polynomial bottom-up t-ts transformations can be characterized by the composition of finite state relabeling t-ts transformations and boolean homomorphism t-ts transformations. Moreover, we prove that every deterministic top-down t-ts transformation can be characterized by the composition of a boolean homomorphism t-ts transformation and a deterministic linear top-down t-ts transformation. We prove that deterministic top-down t-ts transformations are closed under right composition with nondeleting and linear deterministic top-down t-ts transformations and are closed under left composition with boolean and total deterministic top-down t-ts transformations. Finally we show that nondeleting linear bottom-up and nondeleting linear top-down tree series transducers generate the same t-ts transformation class.