The time complexity of typechecking tree-walking tree transducers

DOI10.1007/s00236-008-0087-yzbMath1165.68039OpenAlexW1989452354MaRDI QIDQ1014274

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)

Related Items (3)

Backward type inference for XML queries ⋮ XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Macro forest transducers
• Alternating tree automata
• Typechecking for XML transformers
• A comparison of pebble tree transducers with macro tree transducers
• Tree automata and attribute grammars
• A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars
• Passes and paths of attribute grammars
• Parallel and two-way automata on directed ordered acyclic graphs
• The intrinsically exponential complexity of the circularity problem for attribute grammars
• Complexity of Pebble Tree-Walking Automata
• Semantics of context-free languages

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