The complexity of the exponential output size problem for top-down and bottom-up tree transducers

DOI10.1006/inco.2001.3039zbMath1007.68098OpenAlexW2010727262MaRDI QIDQ1854455

Frank Drewes

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2001.3039

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Branching synchronization grammars with nested tables ⋮ GETGRATS

Cites Work

• Macro tree transducers
• The method of forced enumeration for nondeterministic automata
• Complete problems for deterministic polynomial time
• Haskell overloading is DEXPTIME-complete
• Generalized sequential machine maps
• Nondeterministic Space is Closed under Complementation
• Three hierarchies of transducers
• Mappings and grammars on trees
• Translations on a context free grammar
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of the exponential output size problem for top-down and bottom-up tree transducers