No label defined (Q3779776)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4041315
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4041315

      Statements

      0 references
      0 references
      1987
      0 references
      tree transducers
      0 references
      root-to-frontier tree transformations
      0 references
      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.
      0 references

      Identifiers