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
28 July 1994
0 references
tree automata
0 references
tree transducers
0 references
tree transformation
0 references
0.9716474413871764
0 references
0.8851882815361023
0 references
0.8664306998252869
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