Compression and Ranking

DOI10.1137/0220034MaRDI QIDQ3978781zbMATH OpenOpenAlexFDO

Authors Andrew V. Goldberg, Michael Sipser

Publication date 25 June 1992

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0220034

zbMATH Keywords

data compression

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Theory of data (68P99) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Formal languages and automata (68Q45)

Recommendations

• Recursion-theoretic ranking and compression
• Text and hypertext compression
• Compression and approximate matching
• Pushdown compression
• Indexing compressed text
• scientific article; zbMATH DE number 1552526

Cited in

(21)

• Optimal representation in average using Kolmogorov complexity
• Recursively compressible sets
• The complexity of computing maximal word functions
• Characterizing the existence of one-way permutations
• Recursion-theoretic ranking and compression
• Tally NP sets and easy census functions.
• One-way permutations and self-witnessing languages
• Closure and nonclosure properties of the classes of compressible and rankable sets
• On optimal language compression for sets in PSPACE/poly
• Dimension, entropy rates, and compression
• On the optimal compression of sets in PSPACE
• scientific article; zbMATH DE number 5666625 (Why is no real title available?)
• scientific article; zbMATH DE number 1543032 (Why is no real title available?)
• Rational transductions and complexity of counting problems
• Compression and entropy
• Polynomial-time axioms of choice and polynomial-time cardinality
• Combinatorial generation algorithms based on and/or tree structures for a class of algebraic generating functions
• An efficient coding theorem via probabilistic representations and its applications
• Comparing notions of computational entropy
• Effective entropies and data compression
• Compression of samplable sources

This page was built for publication: Compression and Ranking

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