Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
From MaRDI portal
Publication:3613771
DOI10.1007/11786986_30zbMath1223.68060MaRDI QIDQ3613771
A. Pavan, N. V. Vinodchandran, John M. Hitchcock, Fengming Wang, Lance J. Fortnow
Publication date: 12 March 2009
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11786986_30
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
Related Items
AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES, Optimal bounds for single-source Kolmogorov extractors, Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Extracting Kolmogorov complexity with applications to dimension zero-one laws, Constructive dimension and Turing degrees, Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences, Pushdown dimension, Dimension extractors and optimal decompression, Symmetry of Information: A Closer Look, On the Optimal Compression of Sets in PSPACE, On Generating Independent Random Strings