THE EFFECTIVE ENTROPIES OF SOME EXTENSIONS OF CONTEXT-FREE LANGUAGES

In this paper, we continue our study of the (C1, C2)-effective entropy of a language L, where C1, C2 are complexity classes and L is a language accepted in deterministic polynomial time. The (C1, C2)-effective entropy of a language L is used to measure how much a string x of length less-than-or-equal-to n in L can be compressed to a string y by a C1 algorithm so that given y, x can be recovered by a C2 algorithm. The results are: (1) For any EDOL language L, the (DET, P)-effective entropy of L is equal its absolute entropy, (2) for any degree k simple matrix language L generated by an unambiguous degree k simple matrix grammar, the (NC(2), P)-effective entropy of L is, up to a constant factor, equal its absolute entropy.