Effective entropies and data compression

DOI10.1016/0890-5401(91)90060-FMaRDI QIDQ751832zbMATH OpenFDO

Authors Dung T. Huynh

Publication date 1991

Published in Information and Computation (Search for Journal in Brave)

zbMATH Keywords

complexity classeseffective entropiesentropy of a language

Mathematics Subject Classification ID

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

Recommendations

• The effective entropies of some extensions of context-free languages
• Compression and Ranking
• Compression and entropy
• Toward an abstract theory of data compression
• scientific article; zbMATH DE number 1337738

Cites work

• scientific article; zbMATH DE number 3978426 (Why is no real title available?)
• scientific article; zbMATH DE number 3978429 (Why is no real title available?)
• scientific article; zbMATH DE number 3984573 (Why is no real title available?)
• scientific article; zbMATH DE number 3988704 (Why is no real title available?)
• scientific article; zbMATH DE number 4033108 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 4116450 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• A Mathematical Theory of Communication
• A taxonomy of problems with fast parallel algorithms
• Arithmetic Coding
• Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier Sprachen
• Finite state languages
• Information compression and Varshamov-Gilbert bound
• Log Depth Circuits for Division and Related Problems
• Logarithmic Depth Circuits for Algebraic Functions
• Nondeterministic Space is Closed under Complementation
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• On the Length of Programs for Computing Finite Binary Sequences
• On the entropy of context-free languages
• On uniform circuit complexity
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Tree-size bounded alternation

Cited in

(12)

• On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
• The effective entropies of some extensions of context-free languages
• ?-Entropy data compression
• Internal Compression of Protocols to Entropy
• Computing a context-free grammar-generating series
• How hard is computing the edit distance?
• Statistical mechanics of the data compression theorem
• Rational transductions and complexity of counting problems
• Rational transductions and complexity of counting problems
• Compression of samplable sources
• Epsilon Entropy and Data Compression
• On languages accepted with simultaneous complexity bounds and their ranking problem

This page was built for publication: Effective entropies and data compression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q751832)