Incomparability Results for Classes of Polynomial Tree Series Transformations
Andreas Maletti, Heiko Vogler · 2005
Polynomial bottom-up and top-down tree series transducers over partially ordered semirings are considered, and the classes of $\epsilon$-tree-to-tree-series (for short: $\epsilon$-t-ts) and o-tree-to-tree-series (for short: o-t-ts) transformations computed by such transducers are compared. The main result is the following. Let $A$ be a weakly growing semiring and $x,y \in \{deterministic,homomorphism\}$. The Class of o-t-ts transformations computed by $x$ bottom-up tree series transducers over $A$ is incomparable (with respect to set inclusion) with the class of $\epsilon$-t-ts transformations computed by $y$ bottom-up tree series transducers over $A$. Moreover, the latter class is incomparable with the class of $\epsilon$-t-ts transformations computed by $x$ top-down tree series transducers over $A$. If additionally $A$ is additively idempotent, then the above statements even hold for every $x,y\in \{polynomial,deterministic,homomorphism\}$.