Effective entropies and data compression
From MaRDI portal
Publication:751832
DOI10.1016/0890-5401(91)90060-FzbMath0715.68047MaRDI QIDQ751832
Publication date: 1991
Published in: Information and Computation (Search for Journal in Brave)
Formal languages and automata (68Q45) Measures of information, entropy (94A17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (7)
On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions ⋮ Rational transductions and complexity of counting problems ⋮ On languages accepted with simultaneous complexity bounds and their ranking problem ⋮ Rational transductions and complexity of counting problems ⋮ The effective entropies of some extensions of context-free languages ⋮ How hard is computing the edit distance? ⋮ Computing a context-free grammar-generating series
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Mathematical Theory of Communication
- Information compression and Varshamov-Gilbert bound
- Tree-size bounded alternation
- On uniform circuit complexity
- Finite state languages
- A taxonomy of problems with fast parallel algorithms
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Logarithmic Depth Circuits for Algebraic Functions
- Log Depth Circuits for Division and Related Problems
- Nondeterministic Space is Closed under Complementation
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier Sprachen
- Arithmetic Coding
- On the Length of Programs for Computing Finite Binary Sequences
- On the entropy of context-free languages
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
This page was built for publication: Effective entropies and data compression
