Note on Domain/Surface Tree Languages of t-PDTT's

概要

論文の詳細を見る
String grammars (languages) have been extensively studied from the 60's. On the other hand, the transformational grammar, proposed by N. Chomsky, contains the transformation from the set of derivation trees of a context-free language to the surface set. Here the grammar regarded a tree as an input sentence to some transducer. After that from the second half of 60's, the studies of acceptors, transducers, and so on, whose inputs are trees, have been done extensively. Recently push-down tree automata were introduced, and their fundamental and some other various properties were investigated [12], [13], [22]-[26]. Furthermore a top-down pushdown tree transducer (t-PDTT for short), Which is an extension of a top-down push-down automaton (t-PDTA for short), Was introduced and its fundamental properties were investigated [27]. In this paper we focus on t-PDTT, linear t-PDTT, t-FST (top-down finite state transducer), and t-PDTA. The main subjects discussed here are as follows: (1) the class of domain/surface tree languages of t-PDTT properly contains the class of tree languages accepted by t-PDTA, (2) the class of domain/surface tree languages of linear t-PDTT's coincides with the class of tree languages accepted by t-PDTA's, (3) the class of tree languages accepted by t-PDTA's properly contains the class of surface tree languages of t-FST's.
社団法人電子情報通信学会の論文
1996-06-25