DYCK REDUCTIONS ARE MORE POWERFUL THAN HOMOMORPHIC CHARACTERIZATIONS

Let L be any class of languages, L' be one of the classes of context-f ree, context-sensitive and recursively enumerable languages, and Sigma be any alphabet, In this paper, we show that if the following stateme nt (1) holds, then the statement (2) holds. (1) For any language L in L over Sigma, there exist an alphabet Gamma including Sigma, a homomor phism h:Gamma-->Sigma* defined by h(a)=a for a is an element of Sigma and h(a)=lambda (empty word) for a is an element of Gamma-Sigma, a Dy ck language D over Gamma, and a language L-1 in L' over Gamma such tha t L=h(D boolean AND L-1). (2) For any language L-1 in L over Sigma, th ere exist an alphabet of k pairs of matching parentheses X-k, Dyck red uction Red over X-k. and a language L-2 in L' over Sigma boolean OR X- k such that L=Red(L-2)boolean AND Sigma. We also give an application of this this result.