HOMOMORPHIC CHARACTERIZATIONS ARE MORE POWERFUL THAN DYCK REDUCTIONS

Let L be any class of languages, L' be a class of languages which is c losed under lambda-free homomorphisms, and Sigma be any alphabet. In t his paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Sigma, there ex ist an alphabet of k pairs of matching parentheses X(k), Dyck reductio n Red over X(k), and a language L in L' over Sigma boolean OR X(k) suc h that L=Red(L(1))boolean AND Sigma. (2) For any language L in L over Sigma there exist an alphabet Gamma including Sigma a homomorphism h : Gamma --> Sigma*, a Dyck language D over Gamma, and a language L(2) in L' over Gamma such that L=h(D boolean AND L(2)). We also give an a pplication of this result.