The Complexity of Tree Transducer Output Languages

Kazuhiro Inaba, Sebastian Maneth

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008, December 9-11, 2008, Bangalore, India
Number of pages12
Publication statusPublished - 2008


Dive into the research topics of 'The Complexity of Tree Transducer Output Languages'. Together they form a unique fingerprint.

Cite this