The Complexity of Tree Transducer Output Languages

Inaba, Kazuhiro; Maneth, Sebastian

doi:10.4230/LIPIcs.FSTTCS.2008.1757

Document

The Complexity of Tree Transducer Output Languages

Authors Kazuhiro Inaba, Sebastian Maneth

Part of: Volume: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2008-12-05

PDF

File

LIPIcs.FSTTCS.2008.1757.pdf

Filesize: 434 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2008.1757
URN: urn:nbn:de:0030-drops-17570

Author Details

Kazuhiro Inaba

Sebastian Maneth

Cite As Get 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.

Subject Classification

Keywords

Complexity
Tree Transducer
OI-hierarchy
Context-Sensitive

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail