Independent minimum length programs to translate between given strings

DOI10.1016/S0304-3975(01)00036-6MaRDI QIDQ5958287zbMATH OpenFDO

Authors Nikolai K. Vereshchagin, Michael V. Vyugin

Publication date 3 March 2002

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

Full work available at URL https://doi.org/10.1016/S0304-3975(01)00036-6

zbMATH Keywords

independent programsKolmogorov complexity

Mathematics Subject Classification ID

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

Recommendations

• Computing minimum length representations of sets of words of uniform length
• Computing Minimum Length Representations of Sets of Words of Uniform Length
• Applications of transducers in independent languages, word distances, codes
• Minimization algorithms for sequential transducers
• Minimal synthesis of string to string functions from examples
• String-to-string interpretations with polynomial-size output
• Minimizing resources of sweeping and streaming string transducers
• Minimization of symbolic transducers
• Minimal strings in a regular language with respect to a partial order on the alphabet
• From tree automata to string automata minimization

Cites work

• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• Information distance

Cited in

(8)

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

This page was built for publication: Independent minimum length programs to translate between given strings

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