10.4230/LIPICS.FSTTCS.2008.1757
Inaba, Kazuhiro
Kazuhiro
Inaba
Maneth, Sebastian
Sebastian
Maneth
The Complexity of Tree Transducer Output Languages
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Complexity
Tree Transducer
OI-hierarchy
Context-Sensitive
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
2008
2008-12-05
2008-12-05
2008-12-05
en
urn:nbn:de:0030-drops-17570
10.4230/LIPIcs.FSTTCS.2008
978-3-939897-08-8
1868-8969
10.4230/LIPIcs.FSTTCS.2008
LIPIcs, Volume 2, FSTTCS 2008
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
2
35
244
255
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
2
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
444807 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 244-255