Pushdown machines for the macro tree transducer
type: Item
instance of: scholarly article
title: Pushdown machines for the macro tree transducer
zbMATH Open document ID: 0619.68065
DOI: 10.1016/0304-3975(86)90052-6
author: Joost Engelfriet
author: Heiko Vogler
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
full work available at URL: pushdown-machines-for-the-macro-tree-transducer(1433b707-a9eb-439e-986d-fc83cc997d27).html
review text: The goal of this paper is to find machines which characterize the class of translations induced by macro tree transducers. Roughly speaking, a macro tree transducer can be considered as a machine taking trees as (input) configurations where the label of the root of a tree can be tested and subtrees can be selected (storage type TR). The control of the macro tree transducer consists of a system of recursive function procedures in which calls may occur nestedly and in parallel (control or program type CFT). The general concept of separating program and storage type of a machine proves to be fruitful and it is adhered to throughout. Along with that the idea of storage type simulation is elaborated. The main topic of this paper is to implement the nested recursion inherent in macro tree transducers on pushdown machines, i.e., on machines with a simpler control but a more complicated storage. In a short formula the main results in the total deterministic case are \(D_ tCFT(TR)=D_ tRT(P(TR))\) where the control type RT means recursive function procedures without context parameters, and its analogue for macro tree-to-string transducers. Moreover, characterizations of n-fold compositions of macro tree (-to-string) transducers are established. The proof provides characterizations of CFT(S) and MAC(S) where S is an arbitrary storage type, and it follows the general idea \(''macro=indexed=nested\) stack'': Rather than transforming the known proofs for grammars (S trivial) into proofs for tree transducers uniform proofs for X(S)-transducers are given specializing to both the grammar case and the tree transducer case \((S=TR)\). Indeed, in that way several known results are obtained as corollaries: attribute grammars can be simulated by total deterministic macro tree transducers [\textit{P. Franchi- Zannettacci}, 1982]; the classes of OI context-free languages and of languages accepted by restricted pushdown tree automata coincide [\textit{I. Guessarian}, Math. Syst. Theory 16, …
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q55
zbMATH DE Number: 4005637
zbMATH Keywords: macro tree transducers
zbMATH Keywords: storage type simulation
zbMATH Keywords: pushdown machines
zbMATH Keywords: tree- to-string transducers
zbMATH Keywords: attribute grammars
zbMATH Keywords: macro grammars
zbMATH Keywords: indexed grammars
reviewed by: Markus Kunze
MaRDI profile type: Publication
OpenAlex ID: W2079625718
cites work: Nested Stack Automata
cites work: Indexed Grammars—An Extension of Context-Free Grammars
cites work: Translations on a context free grammar
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: Q3948612
cites work: Bottom-up and top-down tree transformations— a comparison
cites work: Top-down tree transducers with regular look-ahead
cites work: Q3857722
cites work: Q3326871
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. II
cites work: Extended macro grammars and stack controlled machines
cites work: Macro tree transducers
cites work: Q3674077
cites work: Q4179852
cites work: On the power of list iteration
cites work: Full AFLs and nested iterated substitution
cites work: Pushdown tree automata
cites work: Proof of correctness of data representations
cites work: Q5592246
cites work: Tree automata and attribute grammars
cites work: Semantics of context-free languages: Correction
cites work: Attribute Grammars and Mathematical Semantics
cites work: On deterministic indexed languages
cites work: Mappings and grammars on trees
cites work: Some definitional suggestions for automata theory
cites work: Generalized sequential machine maps
cites work: Q4045664
cites work: Q5685626
cites work: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
Recommended article: Macro tree transducers
Recommended article: Corrigenda to: ``Pushdown machines for the macro tree transducer''
Recommended article: A pumping lemma for output languages of macro tree transducers
Recommended article: Q3334094
Recommended article: Q3773371
Recommended article: Multi-Return Macro Tree Transducers
Recommended article: Tree pushdown automata
Recommended article: A comparison of pebble tree transducers with macro tree transducers
Recommended article: Q4259952
Recommended article: Deterministic tree pushdown automata and monadic tree rewriting systems
description: scientific article; zbMATH DE number 4005637