Independent minimum length programs to translate between given strings

DOI10.1016/S0304-3975(01)00036-6zbMath0992.68083MaRDI QIDQ5958287

Michael V. Vyugin, Nikolai K. Vereshchagin

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexityindependent programs

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, INFORMATION DISTANCE AND ITS APPLICATIONS, On Generating Independent Random Strings, Nonapproximability of the normalized information distance, Extracting Kolmogorov complexity with applications to dimension zero-one laws, Conditional complexity and codes, Optimal bounds for single-source Kolmogorov extractors, Dimension extractors and optimal decompression

Cites Work

• Information distance
• Unnamed Item