A complete classification of deterministic root-to-frontier tree transformation classes
type: Item
instance of: scholarly article
title: A complete classification of deterministic root-to-frontier tree transformation classes
zbMATH Open document ID: 0729.68048
DOI: 10.1016/0304-3975(91)90312-P
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
review text: A root-to-frontier tree transducer is a finite-state automaton which transforms trees (terms) into trees by processing the input tree from the root towards the leaves. The class of all tree transformations (TTs) definable by such transducers is denoted by \({\mathcal R}\). Some of the natural restrictions imposed on transducers are determinism (\({\mathcal D})\), linearity (\({\mathcal L})\), the property of being nondeleting (\({\mathcal N})\) or of having just one state, in which case the induced TT is a tree homomorphism (\({\mathcal H})\). Any combination of such requirements leads to a special class of TTs; for example, \({\mathcal L}{\mathcal D}{\mathcal R}\) is the class of TTs definable by linear deterministic root-to-frontier tree transducers, and \({\mathcal N}{\mathcal H}\) is the class of nondeleting tree homomorphisms. If \({\mathcal A}\) and \({\mathcal B}\) are two classes of TTs, their composition \({\mathcal A}\circ {\mathcal B}\) is the class of all relational compositions \(\alpha\circ \beta\), where \(\alpha\in {\mathcal A}\) and \(\beta\in {\mathcal B}.\) The authors present a complete inclusion diagram for all compositions which ca be formed starting from the classes \({\mathcal D}{\mathcal R}\), \({\mathcal L}{\mathcal D}{\mathcal R}\), \({\mathcal N}{\mathcal D}{\mathcal R}\), \({\mathcal L}{\mathcal N}{\mathcal D}{\mathcal R}\), \({\mathcal H}\), \({\mathcal N}{\mathcal H}\) and \({\mathcal L}{\mathcal H}\) (\({\mathcal L}{\mathcal N}{\mathcal H}\) is uninteresting in this context). All pairs of incomparable classes, all proper inclusions and all proper hierarchies are shown to be so. For this a great amount of earlier work done in this area is utilized, but also several new results are needed.
reviewed by: Magnus Steinby
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 4206003
zbMATH Keywords: tree transformations
author: Zoltán Fülöp
author: Sándor Vágvölgyi
MaRDI profile type: MaRDI publication profile
cites work: Composition of top-down and bottom-up tree transductions
cites work: Tree transducers and tree languages
cites work: Bottom-up and top-down tree transformations— a comparison
cites work: On tree transducers for partial functions
cites work: Three hierarchies of transducers
cites work: Top-down tree transducers with regular look-ahead
cites work: A complete rewriting system for a monoid of tree transformation classes
cites work: Q3832055
cites work: Q3813315
cites work: Q3028362
cites work: Q4179852
cites work: Mappings and grammars on trees
cites work: Generalized sequential machine maps
cites work: Q3779776
description: scientific article; zbMATH DE number 4206003