Publication Date

5-25-1993

Technical Report Number

TR93-12

Subjects

Theory of Computation, Data, Computing Methodologies

Abstract

It is known that iterating the look-ahead tree languages for deterministic top-down tree automata, more and more powerful recognizing devices are obtained. Let DR_0 = DR, where DR is the class of all tree languages recognizable by deterministic top-down tree automata, and let, for n >= 1, DR_n be the class of all tree languages recognizable by deterministic top-down tree automata with DR_{n-1} look-ahead. Then, for all n >= 0, DR_n is a proper subset of DR_{n+1} . In a previous paper, Slutzki and Vagvolgyi showed that the composition powers of the class of all deterministic top-down tree transformations with deterministic top-down look-ahead (DTT^{DR}) form a proper hierarchy i.e. (DTT^{DR})^n is a proper subset of (DTT^{DR})^{n+1} (n >= 0) . Along the proof they studied the notion of the deterministic top-down tree transducer with DR_n look-ahead ({dtt}^{DR_n}) and showed that (DTT^{DR})^{n+1} is a subset of DTT^{DR_n} (n >= 0) , where DTT^{DR_n} stands for the class of all tree transformations induced by dtt^{DR_n}'s. Our aim is to show the reversed inclusion, i.e. DTT^{DR_n} is a subset of (DTT^{DR})^{n+1} (n >= 0) . This implies a precise characterization DTT^{DR_n} = (DTT^{DR})^{n+1} (n >= 0) , and implies that the classes DTT^{DR_n} (n >= 0) form a proper hierarchy.

Share

COinS