Compression and Ranking
From MaRDI portal
Publication:3978781
DOI10.1137/0220034zbMath0738.68048OpenAlexW2065703771MaRDI QIDQ3978781
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
Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Theory of data (68P99)
Related Items
One-way permutations and self-witnessing languages, Compression and entropy, Rational transductions and complexity of counting problems, Polynomial-time axioms of choice and polynomial-time cardinality, Recursion-theoretic ranking and compression, Dimension, entropy rates, and compression, Closure and nonclosure properties of the classes of compressible and rankable sets, Comparing notions of computational entropy, Optimal representation in average using Kolmogorov complexity, Characterizing the existence of one-way permutations, Tally NP sets and easy census functions., The complexity of computing maximal word functions
