DETERMINISTIC TOP-DOWN TREE-TRANSDUCERS WITH ITERATED LOOK-AHEAD

It is known that by iterating the look-ahead tree languages for determ inistic top-down tree automata, more and more powerful recognizing dev ices are obtained. Let DR(0) = DR, where DR is the class of all tree l anguages recognizable by deterministic top-down tree automata, and let , for n greater than or equal to 1, DR(n) be the class of all tree lan guages recognizable by deterministic top-down tree automata with DR(n- 1) look-ahead. Then DR(0) subset of DR(1) subset of DR(2) subset of .. .. Slutzki and Vagvolgyi (1993) showed that the composition powers of the class of all deterministic top-down tree transformations with dete rministic top-down look-ahead (DTTDR) form a proper hierarchy, i.e. (D TTDR)(n) subset of (DTTDR)(n+1) for n greater than or equal to 0. Alon g the proof they studied the notion of the deterministic top-down tree transducer with DR(n) look-ahead (dtt(DRn)) and showed that (DTTDR)n1 subset of or equal to DTTDRn (n greater than or equal to 0), where D TTDRn, stands for the class of all tree transformations induced by dtt (DR')s. Our aim is to show the reversed inclusion, i.e. DTTDRn, subset of or equal to (DTTDR)(n+1) (n greater than or equal to 0). This impl ies a precise characterization DTTDRn, = (DTTDR)(n+1) (n greater than or equal to 0),and implies that the classes DTTDRn, (n greater than or equal to 0) form a proper hierarchy.