archives

Deterministic Top-down Tree Transducers with Iterated Look-ahead


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Slutzki, Giora and Vagvolgyi, Sandor (1993) Deterministic Top-down Tree Transducers with Iterated Look-ahead. Technical Report TR93-12, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

Deterministic Top-down Tree Transducers with
Iterated Look-ahead
TR 93-12
by
Giora Slutzki and Sandor Vagvolgyi
Department of Computer Science
Iowa State University
Ames, Iowa 50011, USA
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.

Subjects:All uncategorized technical reports
ID code:00000048
Deposited by:Staff Account on 25 May 1993



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