Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Transducers of polynomial growth ⋮ Attributed tree transducers for partial functions

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