No label defined (Q4273673)

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 475426
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 475426

      Statements

      0 references
      0 references
      28 July 1994
      0 references
      tree automata
      0 references
      tree transducers
      0 references
      tree transformation
      0 references
      In the paper monoids generated by deterministic root-to-frontier tree transformation classes with composition are considered. A procedure is described, which, given a finite and not too general set \(P\) of such tree transformation classes, yields an algorithm with the following property. For any two elements \(X_ 1\circ\ldots\circ X_ m\) and \(Y_ 1\circ\ldots\circ Y_ n\) of the monoid generated by \(P\) with composition \(\circ\), the algorithm can decide if the inclusion \[ X_ 1\circ\ldots\circ X_ m\subseteq Y_ 1\circ\ldots\circ Y_ n \] holds or not. The procedure is applied to two particular choices of \(P\), namely to the sets \[ M=\{DF,LDF,NDF,LNDF,H,LH,NH\} \] and \[ S=\{DR,LDR,NDR,LNDR,H,LH,NH\} \] where the first set consists of the class of deterministic bottom-up tree transformations and its six fundamental subclasses; and the second one consists of the top-dow counterparts of the elements of the first one. For the entire collection see [Zbl 0781.00007].
      0 references

      Identifiers