Incomparability Results for Classes of Polynomial Tree Series Transformations

Polynomial bottom-up and top-down tree series transducers over partially ordered semirings are considered, and the classes of ε-tree-to-tree-series (for short: ε-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 ∈ ,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 ε-t-ts transformations computed by y bottom-up tree series transducers over A. Moreover, the latter class is incomparable with the class of ε-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∈ ,deterministic,homomorphism\.