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

AbstractWe consider the set M={DB, LDB, NDB, LNDB, H, LH, NH} of which the elements are the class of deterministic bottom-up tree transformations (DB), the linear, the nondeleting and the linear, nondeleting subclasses of DB (LDB, NDB and LNDB); the class of homomorphism tree transformations (H), the linear and the nondeleting subclasses of H (LH and NH).The main aim of this paper is to obtain a finite generating system of the equations of the form X1∘⋯∘Xm=Y1∘⋯Yn, where Xi, YjϵM for 1⩽i⩽m, 1⩽j⩽n and ∘ is the composition of tree transformation classes. Therefore, we give a finite Thue system over M, where M is now considered as a seven-letter alphabet, such that two words X1•⋯•Xm and Y1•⋯•Yn of the free monoid M∗ are congruent modulo the Thue congruence ↔T∗ generated by T over M∗ if and only if X1∘⋯∘Xm=Y1∘⋯∘Yn. Moreover, we give a set N of representatives for the congruence ↔T∗ and an inclusion diagram of the tree transformation classes of the form Z1∘⋯∘Zk, where Z1•⋯•ZkϵN. We also present an algorithm, that to each word X1•⋯•XmϵM∗ produces the (unique) representative Z1•⋯•ZkϵN such that X1•⋯•Xm ↔T∗ Z1•⋯•Zk. We prove that, using this algorithm and the inclusion diagram of the tree transformation classes represented by the elements of N, we can decide for any given tree transformation classes X1∘⋯∘Xm and Y1∘⋯∘Yn obtained by composition from elements of M if X1∘⋯∘Xm⊆Y1∘⋯∘Yn and, hence, if X1∘⋯∘Xm= Y1∘⋯∘Yn