Some Notes on Domain Tree Languages of Top-Down Pushdown Tree Transducers

Katsunori YAMASAKI

Some Notes on Domain Tree Languages of Top-Down Pushdown Tree Transducers

Katsunori YAMASAKI

Full Text Views

0

Cite this

Summary :

In this paper, some properties of domain tree languages of top-down pushdown tree transducers (domain(t-PDTT) or t-PDTT_D) are shown. It is shown that (1) for any L₁, L₂ in context-free language (CFL), L₁L₂yield_e(t-PDTT_D) (where yield_e is an extended yield), (2) yield_e(t-PDTT^ε0_DF) is closed under homomorphisms, where t-PDTT^ε0 is a t-PDTT which can not proceed generations after reading a constant symbol σ and t-PDTT^ε0_DF denotes a domain tree language of t-PDTT^ε0 with a final state translation, and (3) yield_e(t-PDTT^ε0_DF) is the class of recursively enumerable languages, and consequently yield_e(t-PDTT_D) is the class of recursively enumerable languages.

Publication: IEICE TRANSACTIONS on Information Vol.E83-D No.9 pp.1713-1720

Publication Date: 2000/09/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Theory of Automata, Formal Language Theory

Cite this

Copy

Katsunori YAMASAKI, "Some Notes on Domain Tree Languages of Top-Down Pushdown Tree Transducers" in IEICE TRANSACTIONS on Information, vol. E83-D, no. 9, pp. 1713-1720, September 2000, doi: .
Abstract: In this paper, some properties of domain tree languages of top-down pushdown tree transducers (domain(t-PDTT) or t-PDTT_D) are shown. It is shown that (1) for any L₁, L₂ in context-free language (CFL), L₁L₂yield_e(t-PDTT_D) (where yield_e is an extended yield), (2) yield_e(t-PDTT^ε0_DF) is closed under homomorphisms, where t-PDTT^ε0 is a t-PDTT which can not proceed generations after reading a constant symbol σ and t-PDTT^ε0_DF denotes a domain tree language of t-PDTT^ε0 with a final state translation, and (3) yield_e(t-PDTT^ε0_DF) is the class of recursively enumerable languages, and consequently yield_e(t-PDTT_D) is the class of recursively enumerable languages.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_9_1713/_p

Copy

@ARTICLE{e83-d_9_1713,
author={Katsunori YAMASAKI, },
journal={IEICE TRANSACTIONS on Information},
title={Some Notes on Domain Tree Languages of Top-Down Pushdown Tree Transducers},
year={2000},
volume={E83-D},
number={9},
pages={1713-1720},
abstract={In this paper, some properties of domain tree languages of top-down pushdown tree transducers (domain(t-PDTT) or t-PDTT_D) are shown. It is shown that (1) for any L₁, L₂ in context-free language (CFL), L₁L₂yield_e(t-PDTT_D) (where yield_e is an extended yield), (2) yield_e(t-PDTT^ε0_DF) is closed under homomorphisms, where t-PDTT^ε0 is a t-PDTT which can not proceed generations after reading a constant symbol σ and t-PDTT^ε0_DF denotes a domain tree language of t-PDTT^ε0 with a final state translation, and (3) yield_e(t-PDTT^ε0_DF) is the class of recursively enumerable languages, and consequently yield_e(t-PDTT_D) is the class of recursively enumerable languages.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - Some Notes on Domain Tree Languages of Top-Down Pushdown Tree Transducers
T2 - IEICE TRANSACTIONS on Information
SP - 1713
EP - 1720
AU - Katsunori YAMASAKI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2000
AB - In this paper, some properties of domain tree languages of top-down pushdown tree transducers (domain(t-PDTT) or t-PDTT_D) are shown. It is shown that (1) for any L₁, L₂ in context-free language (CFL), L₁L₂yield_e(t-PDTT_D) (where yield_e is an extended yield), (2) yield_e(t-PDTT^ε0_DF) is closed under homomorphisms, where t-PDTT^ε0 is a t-PDTT which can not proceed generations after reading a constant symbol σ and t-PDTT^ε0_DF denotes a domain tree language of t-PDTT^ε0 with a final state translation, and (3) yield_e(t-PDTT^ε0_DF) is the class of recursively enumerable languages, and consequently yield_e(t-PDTT_D) is the class of recursively enumerable languages.
ER -