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

Katsunori YAMASAKI

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

Katsunori YAMASAKI

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E79-D No.6 pp.829-839

Publication Date: 1996/06/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Automata,Languages and Theory of Computing

Cite this

Copy

Katsunori YAMASAKI, "Note on Domain/Surface Tree Languages of t-PDTT's" in IEICE TRANSACTIONS on Information, vol. E79-D, no. 6, pp. 829-839, June 1996, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e79-d_6_829/_p

Copy

@ARTICLE{e79-d_6_829,
author={Katsunori YAMASAKI, },
journal={IEICE TRANSACTIONS on Information},
title={Note on Domain/Surface Tree Languages of t-PDTT's},
year={1996},
volume={E79-D},
number={6},
pages={829-839},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={June},}

Copy

TY - JOUR
TI - Note on Domain/Surface Tree Languages of t-PDTT's
T2 - IEICE TRANSACTIONS on Information
SP - 829
EP - 839
AU - Katsunori YAMASAKI
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E79-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 1996
AB - 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.
ER -