Modular tree transducers
type: Item
instance of: scholarly article
title: Modular tree transducers
zbMATH Open document ID: 0729.68018
DOI: 10.1016/0304-3975(91)90353-4
author: Joost Engelfriet
author: Heiko Vogler
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
review text: A new type of term rewriting system, the modular tree transducer (MTT), is introduced as a formal computational model of nested simultaneous primitive recursion on trees. The rules of an MTT are partitioned into numbered modules. These numbers establish the calling structure of the MTT; the module number \(i\) may call only modules with numbers not less than \(i\). It is shown that MTTs compute (almost) exactly the primitive recursive functions on trees, and that one gets a strict hierarchy of tree transduction classes when a increasing number of modules is allowed. The modular tree transducers are natural extensions of macro tree transducers. In fact, the authors prove that by suitably restricting the calling structure, one obtains from the MTTs with \(n\) modules the \(n\)-fold compositions of macro tree transductions (\(n\geq 1)\). The presentation is exemplary in its clarity, the new concepts are carefully motivated, and the important constructions are illustrated by good examples.
reviewed by: Magnus Steinby
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D20
zbMATH DE Number: 4205974
zbMATH Keywords: tree transducer
zbMATH Keywords: primitive recursion
describes a project that uses: ALGOL 60
MaRDI profile type: Publication
full work available at URL: 0304-3975(91)90353-4
OpenAlex ID: W80136255
cites work: Translations on a context free grammar
cites work: Rekursive Wortfunktionen
cites work: Graph expressions and graph rewritings
cites work: Attribute grammars and recursive program schemes. I. II
cites work: Q5612462
cites work: Bottom-up and top-down tree transformations— a comparison
cites work: Q4954439
cites work: Q3326871
cites work: The formal power of one-visit attribute grammars
cites work: IO and OI. II
cites work: Macro tree transducers
cites work: High level tree transducers and iterated pushdown tree transducers
cites work: Q3832055
cites work: Q4179852
cites work: On the power of list iteration
cites work: Q3774975
cites work: Q3785988
cites work: On primitive recursive wordfunctions
cites work: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
cites work: Q4182497
cites work: Q4029598
cites work: A syntax directed compiler for ALGOL 60
cites work: A constructive method for abstract algebraic software specification
cites work: Q3817590
cites work: Semantics of context-free languages
cites work: Q4057549
cites work: Q5581665
cites work: Q3241197
cites work: Q3325707
cites work: Mappings and grammars on trees
cites work: Q5685626
cites work: Generalized sequential machine maps
cites work: Q3755376
description: scientific article; zbMATH DE number 4205974