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.
|Title of host publication||IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008, December 9-11, 2008, Bangalore, India|
|Number of pages||12|
|Publication status||Published - 2008|