The Complexity of Tree Transducer Output Languages

Authors Kazuhiro Inaba, Sebastian Maneth



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2008.1757.pdf
  • Filesize: 434 kB
  • 12 pages

Document Identifiers

Author Details

Kazuhiro Inaba
Sebastian Maneth

Cite AsGet BibTex

Kazuhiro Inaba and Sebastian Maneth. The Complexity of Tree Transducer Output Languages. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 244-255, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1757

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.
Keywords
  • Complexity
  • Tree Transducer
  • OI-hierarchy
  • Context-Sensitive

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail