Publication Date

4-13-1993

Technical Report Number

TR93-10a

Subjects

Computing Methodologies, Data, Theory of Computation

Abstract

The classes DTA, DTT, DTT{DR}, and DTT{R} stand for the family of tree transductions induced by all deterministic top-down tree automata, deterministic top-down tree transducers, deterministic top-down tree transducers with deterministic top-down look-ahead, and deterministic top-down tree transducers with regular look-ahead, respectively. In this paper we study two hierarchies obtained by compositions of tree transformation classes and show that they are proper and that they ``shuffle perfectly''. Using these results we show that the problem of determining the correct inclusion relationship between two arbitrary compositions of tree transformation classes from the set M={ DTA, DTT, DTT{DR}, DTT{R} } can be decided in linear time.

Share

COinS