archives

A Hierarchy of Deterministic Top-down Tree Transformations


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Slutzki, Giora and Vagvolgyi, Sandor (1993) A Hierarchy of Deterministic Top-down Tree Transformations. Technical Report TR93-10a, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

A Hierarchy of Deterministic Top-down Tree Transformations
by
Giora Slutzki and Sandor Vagvolgyi
Department of Computer Science
Iowa State University
Ames, Iowa  50011, USA
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.

Subjects:All uncategorized technical reports
ID code:00000046
Deposited by:Staff Account on 13 April 1993



Contact site administrator at: ssg@cs.iastate.edu