A complete classification of deterministic root-to-frontier tree transformation classes (Q807029)

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.