文章基本信息

标题：The Complexity of Tree Transducer Output Languages
本地全文：下载
作者：Kazuhiro Inaba ; Sebastian Maneth
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2008
卷号：2
页码：244-255
DOI：10.4230/LIPIcs.FSTTCS.2008.1757
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Complexity; Tree Transducer; OI-hierarchy; Context-Sensitive