Decidability of the shape preserving property of bottom-up tree transducers
It is a known result that both shape preserving top-down tree transducers and shape preserving bottom-up tree transducers are semantically equivalent to finite state relabeling tree transducers. Moreover, it is also known that the shape preserving property of top-down tree transducers is decidable. In this paper we present an analogous result for bottom-up tree transducers: we show that it is also decidable whether a bottom-up tree transducer is shape preserving or not.
bottom-up tree transducers top-down tree transducers tree automata