The Complexity of Tree Transducer Output Languages

Kazuhiro Inaba & Sebastian Maneth
Two complexity results are shown for the output languages generated by compositions of macro tree transducers. They are in $\NSPACE(n)$ and hence are context-sensitive, and the class is NP-complete.