Paper Info
Title
The Complexity of Tree Transducer Output Languages
Abstract
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.
Year
DOI
Venue
2008
10.4230/LIPIcs.FSTTCS.2008.1757
FSTTCS
Field
DocType
Citations 
Tree transducers,Transducer,Discrete mathematics,Computer science,NSPACE,Macro
Conference
6
PageRank 
References 
Authors
0.48
21
2
Name
Order
Citations
PageRank
Kazuhiro Inaba11028.07
Sebastian Maneth297561.51