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.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.