The Complexity of Tree Transducer Output Languages

DOI10.4230/LIPICS.FSTTCS.2008.1757MaRDI QIDQ3165963zbMATH OpenOpenAlexFDO

Authors Kazuhiro Inaba, Sebastian Maneth

Publication date 19 October 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_3b11.html

zbMATH Keywords

complexitycontext-sensitiveOI-hierarchytree transducer

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1954390
• The complexity of the exponential output size problem for top-down and bottom-up tree transducers
• scientific article; zbMATH DE number 475424
• On the Complexity of the Syntax of Tree Languages
• scientific article; zbMATH DE number 3945364
• Publication:4934332
• The Complexity of Tree Automata and Logics of Programs
• The output size problem for string-to-tree transducers
• scientific article; zbMATH DE number 3858448
• scientific article; zbMATH DE number 4108162

Cited in

(7)

• The time complexity of typechecking tree-walking tree transducers
• Computation tree measurement language (CTML)
• The complexity of the exponential output size problem for top-down and bottom-up tree transducers
• Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
• Formal efficiency analysis for tree transducer composition
• Polynomial-time inverse computation for accumulative functions with multiple data traversals
• Implementation and Application of Automata

This page was built for publication: The Complexity of Tree Transducer Output Languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3165963)