A Hierarchy of Deterministic Top-down Tree Transformations

Date
1993-04-13
Authors
Slutzki, Giora
Vagvolgyi, Sandor
Journal Title
Journal ISSN
Volume Title
Publisher
Source URI
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue
Series
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.

Description
Keywords
Citation
Collections