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