Compression and Ranking
Copyright policy )Compression and Ranking
A notion of language compressibility is defined and it is proved that in a sufficiently sparse and ``easy''-computable language essentially all strings can be compressed efficiently. Similar results hold for a type of optimal compression (ranking). Examples of languages that cannot be compressed/ranked efficiently are also presented, as well as some relations with Kolmogorov complexity and randomness.
- Massachusetts Institute of Technology United States
- University of California, Berkeley United States
Complexity of computation (including implicit computational complexity), Theory of data, Formal languages and automata, data compression, Algorithmic information theory (Kolmogorov complexity, etc.)
Complexity of computation (including implicit computational complexity), Theory of data, Formal languages and automata, data compression, Algorithmic information theory (Kolmogorov complexity, etc.)
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).76 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!