Effective entropies and data compression. (English) Zbl 0715.68047

Summary: We introduce the formal definition of the concept of the (\({\mathcal C}_ 1,{\mathcal C}_ 2)\)-effective entropy of a language, where \({\mathcal C}_ 1\), \({\mathcal C}_ 2\) are complexity classes. The (\({\mathcal C}_ 1,{\mathcal C}_ 2)\)-effective entropy of a language L is used to measure how much a string x of length \(\leq n\) in L can be compressed to a string y by a \({\mathcal C}_ 1\) algorithm so that given y, x can be recovered by a \({\mathcal C}_ 2\) algorithm. We also relate this concept to issues in data compression. The main results are: (1) The \(SC^{(j)}\)-effective entropy of a \(2^{O(\log n)}\)-sparse regular language is equal its absolute entropy, i.e., it is optimal; (2) the \((DET,SC^{(j)})\)-effective entropy of a \(2^{O(\log n)}\)-sparse, \(2^{O(\log n)}\)-ambiguous linear context-free language is, up to a constant factor, equal its absolute entropy (DET denotes the class of problems which are \(NC^{(1)}\)- reducible to computing the determinants of integer matrices); and (3) the \((NC^{(2)},P)\)-effective entropy of a \(2^{O(\log n)}\)-sparse, \(2^{O(\log n)}\)-ambiguous context-free language is, up to a constant factor, equal its absolute entropy.


68Q45 Formal languages and automata
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
94A17 Measures of information, entropy
Full Text: DOI


[1] Allender, E., Invertible functions, ()
[2] Allender, E., The complexity of sparse sets in P, (), 1-11
[3] Alt, H., Eine untere schranke für den platzbedarf bei der analyse beschränkter kontextfreier sprachen, () · Zbl 0373.68043
[4] Beame, P.; Cook, S.; Hoover, J., Log depth circuits for division and related problems, SIAM J. comput., 15, 994-1003, (1986) · Zbl 0619.68047
[5] Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. comput., 6, 305-322, (1977) · Zbl 0356.68059
[6] Bertoni, A.; Goldwurm, M.; Sabadini, N., Computing the counting function of context-free languages, (), 169-179 · Zbl 0634.68069
[7] Blahut, R., ()
[8] Chaitin, G.J., On the length of programs for computing finite binary sequences, J. assoc. comput. Mach., 13, 547-569, (1966) · Zbl 0158.25301
[9] Chomsky, N.; Miller, G., Finite state languages, Inform. and control, 1, 91-112, (1958) · Zbl 0081.14503
[10] Cook, S., An overview of computational complexity (Turing award lecture), Comm. ACM, 26, 401-408, (1982)
[11] Cook, S., A taxonomy of problems which have fast parallel algorithms, Inform. and comput., 64, 2-22, (1985) · Zbl 0575.68045
[12] Ginsburg, S., ()
[13] Goldberg, A.; Sipser, M., Compression and ranking, (), 440-448
[14] Hartmanis, J., Generalized Kolmogorov complexity and the structure of feasible computations, (), 439-445
[15] Hemachandra, L., On ranking, (), 103-117
[16] Hopcroft, J.; Ullman, J., ()
[17] Huynh, D.T., Resource-bounded Kolmogorov complexity of hard languages, (), 181-195
[18] Huynh, D.T., The complexity of ranking, (), 204-212
[19] Ibarra, O.; Ravikumar, B., On sparseness, ambiguity and other decision problems for acceptors and transducers, (), 171-179 · Zbl 0605.68080
[20] {\scIbarra, O., Jiang, T., Ravikumar, B., and Chang, J.} (1987), On some languages in NC(1), manuscript.
[21] Immerman, N., Nondeterministic space Is closed under complement, () · Zbl 0668.68056
[22] Kolmogorov, A.N., Three approaches for defining the concept of information quantity, Problems inform. transmission, 1, 1-7, (1965)
[23] Krichevsky, R., Information compression and varshamov-Gilbert bound, Inform. and comput., 74, 1-14, (1987) · Zbl 0637.94004
[24] Kuich, W., On the entropy of context-free languages, Inform. and control, 6, 173-200, (1970) · Zbl 0193.32603
[25] Reif, J., Logarithmic depth circuits for algebraic functions, SIAM J. comput., 15, 231-242, (1986) · Zbl 0611.68014
[26] Rissanen, J.; Langdon, G., Arithmetic coding, IBM J. res. develop., 23, 149-162, (1979) · Zbl 0404.94005
[27] Ruzzo, W., Tree-size bounded alternation, J. comput. system sci., 21, 218-235, (1980) · Zbl 0445.68034
[28] Ruzzo, W., On uniform circuit complexity, J. comput. system sci., 22, 365-383, (1981) · Zbl 0462.68013
[29] Rytter, W., On the recognition of context-free languages, (), 318-325
[30] Salomaa, A.; Soittola, M., Automata-theoretic aspects of formal power series, () · Zbl 0377.68039
[31] Shannon, C., A mathematical theory of communication, Bell system tech. J., 27, 379-423, (1948) · Zbl 1154.94303
[32] Sipser, M., A complexity theoretic approach to randomness, (), 330-335
[33] Stearns, R.; Hunt, H., On the equivalence and containment problem for unambiguous regular expressions, regular grammars and finite automata, (), 74-81 · Zbl 0577.68074
[34] Tarjan, R.; Vishkin, U., Finding biconnected components and computing tree functions in logarithmic parallel time, (), 12-20
[35] Yao, A.C., Theory and applications of trapdoor functions, (), 80-91
[36] Zvonkin, A.K.; Levin, L.A., The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian math. surveys, 25, 83-124, (1970) · Zbl 0222.02027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.