COMPOSITIONS OF DETERMINISTIC BOTTOM-UP, TOP-DOWN, AND REGULAR LOOK-AHEAD TREE-TRANSFORMATIONS

We show that DTR = DT circle LDB, that LDT(R) not subset of or equal t o LDT circle DB, and that DT not subset of or equal to LDT(R) circle H , where DB, DT, H stand for the class of deterministic bottom-up tree transformations, the class of deterministic top-down tree transformati ons, and the class of homomorphism tree transformations, respectively. The prefix L stands for the adjective linear, and the superscript R s tands for the regular look-ahead. The composition of tree transformati on classes X and Y is denoted by X circle Y. Using these results and t he composition and inclusion results of Engelfriet, Fulop, and Fulop a nd Vagvolgyi we show that the problem of determining the correct inclu sion relationship between two arbitrary compositions of tree transform ation classes from the set {DTR, LDT(R), DT, LDT, DB, LDB, H, LH} can be decided in linear time.