scientific article; zbMATH DE number 475426

From MaRDI portal
Publication:4273673





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].











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 Q4273673)