Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
From MaRDI portal
Publication:2022308
DOI10.1007/s00236-019-00360-8OpenAlexW2995724076MaRDI QIDQ2022308
Kazuhiro Inaba, Sebastian Maneth, Joost Engelfriet
Publication date: 28 April 2021
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.09203
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Automata for XML -- a survey
- The time complexity of typechecking tree-walking tree transducers
- Macro forest transducers
- Increasing modularity and language-independency in automatically generated compilers
- Macro tree transducers
- Alternating tree automata
- High level tree transducers and iterated pushdown tree transducers
- Composition and evaluation of attribute coupled grammars
- The OI-hierarchy is closed under control
- Tree-size bounded alternation
- The formal power of one-visit attribute grammars
- The IO- and OI-hierarchies
- Attribute grammars and recursive program schemes. I. II
- Attribute grammars. Definitions, systems and bibliography
- The membership question for ETOL-languages is polynomially complete
- IO and OI. II
- On tree transducers for partial functions
- Monadic second-order definable graph transductions: a survey
- Typechecking for XML transformers
- A comparison of pebble tree transducers with macro tree transducers
- A comparison of tree transductions defined by monadic second order logic and by attribute grammars
- Output string languages of compositions of deterministic macro tree transducers
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
- Generalized sequential machine maps
- Tree acceptors and some of their applications
- A Survey on Decidable Equivalence Problems for Tree Transducers
- The Complexity of Tree Transducer Output Languages
- Multi-Return Macro Tree Transducers
- Tree-Walking Automata Do Not Recognize All Regular Languages
- The Complexity of Languages Generated by Attribute Grammars
- Time and space complexity of inside-out macro languages
- Alternation
- Bottom-up and top-down tree transformations— a comparison
- Top-down tree transducers with regular look-ahead
- Generalized Syntax Directed Translation, Tree Transducers, and Linear Space
- On the Tape Complexity of Deterministic Context-Free Languages
- Macro Tree Translations of Linear Size Increase are MSO Definable
- Type Checking of Tree Walking Transducers
- Equality and disequality constraints on direct subterms in tree automata
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- Unsafe Order-2 Tree Languages Are Context-Sensitive
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Semantics of context-free languages
- Indexed Grammars—An Extension of Context-Free Grammars
- Mappings and grammars on trees
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Translations on a context free grammar
This page was built for publication: Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
