The time complexity of typechecking tree-walking tree transducers

DOI10.1007/S00236-008-0087-YMaRDI QIDQ1014274zbMATH OpenOpenAlexFDO

Authors Joost Engelfriet

Publication date 27 April 2009

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-008-0087-y

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Type checking of tree walking transducers
• The Complexity of Tree Transducer Output Languages
• scientific article; zbMATH DE number 1953124
• scientific article; zbMATH DE number 1954390
• Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
• STACS 2004
• Formal efficiency analysis for tree transducer composition
• The complexity of the exponential output size problem for top-down and bottom-up tree transducers
• scientific article; zbMATH DE number 3858448

Cites work

• A comparison of pebble tree transducers with macro tree transducers
• A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars
• Alternating tree automata
• Complexity of Pebble Tree-Walking Automata
• scientific article; zbMATH DE number 3740783 (Why is no real title available?)
• scientific article; zbMATH DE number 3789855 (Why is no real title available?)
• scientific article; zbMATH DE number 1200800 (Why is no real title available?)
• scientific article; zbMATH DE number 1948151 (Why is no real title available?)
• scientific article; zbMATH DE number 5254145 (Why is no real title available?)
• Macro forest transducers
• Parallel and two-way automata on directed ordered acyclic graphs
• Passes and paths of attribute grammars
• Semantics of context-free languages
• The intrinsically exponential complexity of the circularity problem for attribute grammars
• Tree automata and attribute grammars
• Typechecking for XML transformers

Cited in

(7)

• Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
• Backward type inference for XML queries
• XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
• XML Type Checking Using High-Level Tree Transducer
• scientific article; zbMATH DE number 1953124 (Why is no real title available?)
• Type checking of tree walking transducers
• Slightly nonlinear higher-order tree transducers

This page was built for publication: The time complexity of typechecking tree-walking tree transducers

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