The complexity of the exponential output size problem for top-down and bottom-up tree transducers
From MaRDI portal
Publication:1854455
DOI10.1006/inco.2001.3039zbMath1007.68098OpenAlexW2010727262MaRDI QIDQ1854455
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
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)
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