Homomorphic Characterizations Are More Powerful Than Dyck Reductions

Let L be any class of languages, L\u27 be a class of languages which is closed under λ-free homomorphisms, 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 of k pairs of matching parentheses X_k, Dyck reduction Red over X_k, and a language L_1 in L\u27 over Σ⋃X_k such that L=Red(L_1)⋂Σ^*. (2) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h : Γ^*→Σ^*, a Dyck language D over Γ, and a language L_2 in L\u27 over Γ such that L=h(D⋂L_2). We also give an application of this result