scientific article; zbMATH DE number 4041315

From MaRDI portal
Publication:3779776





For any two classes of tree transformations \({\mathcal K}\) and \({\mathcal L}\), let \({\mathcal K}\circ {\mathcal L}\) denote the class of all compositions \(\kappa\circ \lambda\) where \(\kappa\in {\mathcal K}\) and \(\lambda\in {\mathcal L}\). The authors continue here their studies of such composition classes obtained by starting with certain basic subclasses of the class \({\mathcal D}{\mathcal R}\) of deterministic root-to-frontier tree transformations [cf. the authors, ibid. 8, 49-61 (1987; Zbl 0625.68060)]. Let \({\mathcal L}{\mathcal N}{\mathcal D}{\mathcal R}\) be the class of all linear, nondeleting, deterministic root-to-frontier tree transformations, and let \({\mathcal N}{\mathcal H}\) be the class of all non-deleting tree homomorphisms. It is proved that the powers (\({\mathcal L}{\mathcal N}{\mathcal D}{\mathcal R}\circ {\mathcal N}{\mathcal H})^ m\) form a strictly ascending hierarchy for \(m=1,2,... \). This shows that the set of subclasses of \({\mathcal D}{\mathcal R}\) considered in the above mentioned paper is infinite. Moreover, the authors prove that the union of these powers is a proper subclass of \({\mathcal N}{\mathcal D}{\mathcal R}\), the class of all non-deleting \({\mathcal D}{\mathcal R}\) transformations.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3779776)