Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
type: Item
instance of: scholarly article
title: Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
author: Joost Engelfriet
author: Kazuhiro Inaba
author: Sebastian Maneth
published in: Acta Informatica
publication date: 2021-04-28T00:00:00Z
full work available at URL: https://arxiv.org/abs/1904.09203
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7340920
MaRDI profile type: Publication
OpenAlex ID: W2995724076
cites work: Indexed Grammars—An Extension of Context-Free Grammars
cites work: Translations on a context free grammar
cites work: Time and space complexity of inside-out macro languages
cites work: Generalized Syntax Directed Translation, Tree Transducers, and Linear Space
cites work: Q3967069
cites work: Q4362731
cites work: A comparison of tree transductions defined by monadic second order logic and by attribute grammars
cites work: Equality and disequality constraints on direct subterms in tree automata
cites work: Tree-Walking Automata Do Not Recognize All Regular Languages
cites work: Alternation
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: Monadic second-order definable graph transductions: a survey
cites work: Q3077955
cites work: Attribute grammars and recursive program schemes. I. II
cites work: The IO- and OI-hierarchies
cites work: Attribute grammars. Definitions, systems and bibliography
cites work: Tree acceptors and some of their applications
cites work: Bottom-up and top-down tree transformations— a comparison
cites work: Top-down tree transducers with regular look-ahead
cites work: On tree transducers for partial functions
cites work: Q3340111
cites work: The Complexity of Languages Generated by Attribute Grammars
cites work: The time complexity of typechecking tree-walking tree transducers
cites work: The formal power of one-visit attribute grammars
cites work: XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
cites work: Macro tree transducers, attribute grammars, and MSO definable tree translations.
cites work: Output string languages of compositions of deterministic macro tree transducers
cites work: A comparison of pebble tree transducers with macro tree transducers
cites work: Macro Tree Translations of Linear Size Increase are MSO Definable
cites work: IO and OI. II
cites work: Macro tree transducers
cites work: High level tree transducers and iterated pushdown tree transducers
cites work: Q3906457
cites work: Q3925893
cites work: Q4210160
cites work: Increasing modularity and language-independency in automatically generated compilers
cites work: Q4198056
cites work: Q3323279
cites work: Composition and evaluation of attribute coupled grammars
cites work: Q4198075
cites work: Q3058276
cites work: Multi-Return Macro Tree Transducers
cites work: The Complexity of Tree Transducer Output Languages
cites work: Semantics of context-free languages
cites work: Unsafe Order-2 Tree Languages Are Context-Sensitive
cites work: Q4380987
cites work: Q4415261
cites work: FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
cites work: A survey on decidable equivalence problems for tree transducers
cites work: Type Checking of Tree Walking Transducers
cites work: Typechecking for XML transformers
cites work: Q4298260
cites work: Macro forest transducers
cites work: Mappings and grammars on trees
cites work: Tree-size bounded alternation
cites work: Automata for XML -- a survey
cites work: Alternating tree automata
cites work: On the Tape Complexity of Deterministic Context-Free Languages
cites work: Generalized sequential machine maps
cites work: Generalized finite automata theory with an application to a decision problem of second-order logic
cites work: The membership question for ETOL-languages is polynomially complete
cites work: The OI-hierarchy is closed under control
DOI: 10.1007/S00236-019-00360-8
description: scientific article; zbMATH DE number 7340920