The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] domain (surface) tree languages(1hit)

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

    Katsunori YAMASAKI  

     
    PAPER-Automata,Languages and Theory of Computing

      Vol:
    E79-D No:6
      Page(s):
    829-839

    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 pushdown 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 pushdown 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.