A complete rewriting system for a monoid of tree transformation classes

AbstractWe take the set S of the seven fundamental deterministic root-to-frontier tree transformation classes DR, LDR, NDR, L.NDR, H, LH, and NH, where DR (H) is the calss of all deterministic root-to-frontier (resp. homomorphism) tree transformations and the prefixes L, N, and LN mean the linear, the nondeleting and the linear, nondeleting subclasses, respectively. We examine the monoid [S] generated by S with composition. We give a finite, complete rewriting system R over S (where the elements of S are considered now as denotations of the corresponding tree transformation classes) such that every element of R, viewed as a formal equation, is valid in [S] and that R presents [S], i.e., [S]≅S∗/↔∗R with ↔∗R being the Thue congruence generated by R on the free monoid S∗. Moreover, it is shown that the word problem of S∗/↔∗R is decidable in linear time