A complete description for a monoid of deterministic bottom-up tree transformation classes (Q1177164)

Let \(DB\) denote the class of tree transformations defined by deterministic bottom-up (frontier-to-root) tree transducers. The subclasses of \(DB\) obtained by requiring that all rules of the transducers are deterministic or nondeleting, or both, are denoted by \(LDB\), \(NDB\) and \(LNDB\), respectively. One-state transducers yield the class \(H\) of tree homomorphisms. The subclasses \(LH\) and \(NH\) are defined in the natural way. The composition \(A\circ B\) of two classes \(A\) and \(B\) of tree transformations is the class of all relational compositions \(\alpha\circ\beta\), where \(\alpha\in A\) and \(\beta\in B\). The author studies the monoid \([M]\) generated by the set \(M=\{DB,LDB,NDB,LNDB,H,LH,NH\}\). It is finite and a complete inclusion diagram showing the relationships between its elements is given. The monoid \([M]\) is isomorphic to the quotient monoid \(M^*/\theta\), where \(\theta\) is the kernel of the homomorphism from \(M^*\) to \([M]\) which maps each word \(X_ 1X_ 2\dots X_ n\) to the class \(X_ 1\circ X_ 2\circ\dots\circ X_ n\). The author gives a finite Thue system which generates \(\theta\). Hence, a finite presentation of \([M]\) is obtained, and then the word problem of \([M]\) is proved to be decidable. In fact, the inclusion problem \(``X_ 1\circ\dots\circ X_ m\subseteq Y_ 1\circ\dots\circ Y_ n\)?'' of composition classes formed from elements of \(M\) is decidable.