Top-down tree transducers with two-way tree walking look-ahead (Q1185007)

Top-down tree transducers with regular look-ahead were introduced by \textit{J. Engelfriet} [Math. Systems Theory 10, 289-303 (1977; Zbl 0369.68048)]. The idea was to strengthen topdown transducers by allowing the applicability of transformation rules to be conditional upon the membership of subtrees of the input tree in some given regular tree languages. The author considers top-down tree-transducers in which two- way tree-walking automata perform a look-ahead checking. In fact, several types of such transducers are obtained when the look-ahead automata may be deterministic, nondeterministic or universal, and the basic transducer itself may be deterministic or strictly deterministic. The inclusion relationships between the various classes of tree transformations involved are clarified. Moreover, the paper contains several composition and composition results. For example, it is shown that any top-down tree transformation with regular look-ahead can be decomposed into a deterministic top-down transformation followed by a top-down transformation with tree-walking look-ahead. Finally, it is shown that some of the classes of tree transformations with tree-walking look-ahead have finite composition power hierarchies while others yield infinite hierarchies.