Dyck Reductions are More Powerful Than Homomorphic Characterizations

概要

論文の詳細を見る
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_1 in L' over Γ such that L=h(D∩L_1). (2) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses Χ_k, Dyck reduction Red over Χ_k, and a language L_2 in L' over Σ∪Χ_k such that L=Red(L_2)∩Σ^*. We also give an application of this result.
社団法人電子情報通信学会の論文
1997-09-25