Dyck Reductions are More Powerful Than Homomorphic Characterizations

Sadaki HIROSE; Satoshi OKAWA; Haruhiko KIMURA

Dyck Reductions are More Powerful Than Homomorphic Characterizations

Sadaki HIROSE, Satoshi OKAWA, Haruhiko KIMURA

Full Text Views

0

Cite this

Summary :

Let L be any class of languages, L' be one of the classes of context-free, context-sensitive and recursively enumerable languages, and Σ be any alphabet. In this paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h:Γ^*Σ^* defined by h(a)=a for aΣ and h(a)=λ (empty word) for aΓ-Σ, a Dyck language D over Γ, and a language L₁ in L' over Γ such that L=h(DL₁). (2) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses X_k, Dyck reduction Red over X_k, and a language L₂ in L' over ΣX_k such that L=Red(L₂)Σ^*. We also give an application of this result.

Publication: IEICE TRANSACTIONS on Information Vol.E80-D No.9 pp.958-961

Publication Date: 1997/09/25

Publicized

Online ISSN

DOI

Type of Manuscript

Category: Automata,Languages and Theory of Computing

Cite this

Copy

Sadaki HIROSE, Satoshi OKAWA, Haruhiko KIMURA, "Dyck Reductions are More Powerful Than Homomorphic Characterizations" in IEICE TRANSACTIONS on Information, vol. E80-D, no. 9, pp. 958-961, September 1997, doi: .
Abstract: Let L be any class of languages, L' be one of the classes of context-free, context-sensitive and recursively enumerable languages, and Σ be any alphabet. In this paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h:Γ^*Σ^* defined by h(a)=a for aΣ and h(a)=λ (empty word) for aΓ-Σ, a Dyck language D over Γ, and a language L₁ in L' over Γ such that L=h(DL₁). (2) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses X_k, Dyck reduction Red over X_k, and a language L₂ in L' over ΣX_k such that L=Red(L₂)Σ^*. We also give an application of this result.
URL: https://global.ieice.org/en_transactions/information/10.1587/e80-d_9_958/_p

Copy

@ARTICLE{e80-d_9_958,
author={Sadaki HIROSE, Satoshi OKAWA, Haruhiko KIMURA, },
journal={IEICE TRANSACTIONS on Information},
title={Dyck Reductions are More Powerful Than Homomorphic Characterizations},
year={1997},
volume={E80-D},
number={9},
pages={958-961},
abstract={Let L be any class of languages, L' be one of the classes of context-free, context-sensitive and recursively enumerable languages, and Σ be any alphabet. In this paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h:Γ^*Σ^* defined by h(a)=a for aΣ and h(a)=λ (empty word) for aΓ-Σ, a Dyck language D over Γ, and a language L₁ in L' over Γ such that L=h(DL₁). (2) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses X_k, Dyck reduction Red over X_k, and a language L₂ in L' over ΣX_k such that L=Red(L₂)Σ^*. We also give an application of this result.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - Dyck Reductions are More Powerful Than Homomorphic Characterizations
T2 - IEICE TRANSACTIONS on Information
SP - 958
EP - 961
AU - Sadaki HIROSE
AU - Satoshi OKAWA
AU - Haruhiko KIMURA
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E80-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 1997
AB - Let L be any class of languages, L' be one of the classes of context-free, context-sensitive and recursively enumerable languages, and Σ be any alphabet. In this paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h:Γ^*Σ^* defined by h(a)=a for aΣ and h(a)=λ (empty word) for aΓ-Σ, a Dyck language D over Γ, and a language L₁ in L' over Γ such that L=h(DL₁). (2) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses X_k, Dyck reduction Red over X_k, and a language L₂ in L' over ΣX_k such that L=Red(L₂)Σ^*. We also give an application of this result.
ER -