| Popis: |
We denote the class of deterministic top-down tree transformations by DT and the class of homomorphism tree transformations by HOM . The sign of a class with the prefix l - ( sl -, nd -) denotes the linear ( superlinear, nondeleting ) subclass of that class. We fix the set M = HOM , sl - DT , l - DT , nd - DT , DT of tree transformation classes. Then consider the monoid [ M ] of all tree transformation classes of the form X 1 O … OX m , where O is the operation composition, m ⩾ 0 and the X i 's are elements of M . As the main result of the paper, we give an effective description of the monoid [ M ] with respect to inclusion. This means that we present an algorithm which can decide, given arbitrary two elements of the monoid, whether some inclusion, equality or incomparability holds between them. |
Full Text from ScienceDirect