High level tree transducers and iterated pushdown tree transducers
type: Item
instance of: scholarly article
title: High level tree transducers and iterated pushdown tree transducers
zbMATH Open document ID: 0633.68073
DOI: 10.1007/BF02915449
author: Joost Engelfriet
author: Heiko Vogler
published in: Acta Informatica
publication date: 1988-01-01T00:00:00Z
review text: n-level tree transducers (n\(\geq 0)\) combine the features of n-level tree grammars and of top-down tree transducers in the sense that the derivations of the tree grammars are syntax-directed by input trees. For running n, the sequence of n-level tree transducers starts with top-down tree transducers \((n=0)\) and macro tree transducers \((n=1)\). In this paper the class of tree-to-tree translations computed by n-level tree transducers is characterized by n-iterated pushdown tree transducers. Such a transducer can be considered as a regular tree grammar of which the derivations are syntax-directed by n-iterated pushdown of trees; an n-iterated pushdown of trees is a pushdown of pushdowns of... of pushdowns (n times) of trees. In particular, we investigate the total deterministic case, which is relevant for syntax-directed semantics of programming languages.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q55
Mathematics Subject Classification ID: 68Q60
zbMATH DE Number: 4031018
zbMATH Keywords: tree transducers
zbMATH Keywords: tree grammars
zbMATH Keywords: syntax-directed semantics of programming languages
MaRDI profile type: Publication
cites work: Translations on a context free grammar
cites work: Tree generating regular systems
cites work: An order-algebraic definition of knuthian semantics
cites work: Attribute grammars and recursive program schemes. I. II
cites work: The IO- and OI-hierarchies
cites work: An automata-theoretical characterization of the OI-hierarchy
cites work: Q3933779
cites work: Bottom-up and top-down tree transformations— a comparison
cites work: Top-down tree transducers with regular look-ahead
cites work: Three hierarchies of transducers
cites work: The formal power of one-visit attribute grammars
cites work: Tree transducers, L systems, and two-way machines
cites work: IO and OI. I
cites work: Macro tree transducers
cites work: Q3334094
cites work: Pushdown machines for the macro tree transducer
cites work: Q3738591
cites work: Q3323279
cites work: Full AFLs and nested iterated substitution
cites work: Pushdown tree automata
cites work: Q5592246
cites work: Semantics of context-free languages
cites work: A generalized approach to formal languages
cites work: Mappings and grammars on trees
cites work: Some definitional suggestions for automata theory
cites work: Generalized sequential machine maps
cites work: The OI-hierarchy is closed under control
cites work: Q4045664
cites work: Q3340111
full work available at URL: https://doi.org/10.1007/bf02915449
OpenAlex ID: W2061491534
Recommended article: Q3738591
Recommended article: Q3326871
Recommended article: Q3716312
Recommended article: Deterministic top-down tree transducers with iterated look-ahead
Recommended article: Recursively defined tree transductions
Recommended article: The Power of Extended Top-Down Tree Transducers
Recommended article: Symbolic Tree Transducers
Recommended article: Iterated relabeling tree transducers
Recommended article: Q4269222
Recommended article: Q5089205
description: scientific article; zbMATH DE number 4031018