Counting dependent and independent strings

DOI10.1007/978-3-642-15155-2_60MaRDI QIDQ3586123zbMATH OpenOpenAlexFDO

Authors Marius Zimand

Publication date 3 September 2010

Published in Mathematical Foundations of Computer Science 2010 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.1315

Mathematics Subject Classification ID

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

Abstract: The paper gives estimations for the sizes of the the following sets: (1) the set of strings that have a given dependency with a fixed string, (2) the set of strings that are pairwise alpha independent, (3) the set of strings that are mutually alpha independent. The relevant definitions are as follows: C(x) is the Kolmogorov complexity of the string x. A string y has alpha -dependency with a string x if C(y) - C(y|x) geq alpha. A set of strings {x_1, ldots, x_t} is pairwise alpha-independent if for all i different from j, C(x_i) - C(x_i | x_j) leq alpha. A tuple of strings (x_1, ldots, x_t) is mutually alpha-independent if C(x_{pi(1)} ldots x_{pi(t)}) geq C(x_1) + ldots + C(x_t) - alpha, for every permutation pi of [t].

Recommendations

• Sets of K-independent strings
• On generating independent random strings
• Generating Kolmogorov random strings from sources with limited independence
• Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
• Systems of strings with high mutual complexity

Cited in

(10)

• Counting distinct strings
• A note on the number of N-bit strings with maximum complexity
• Systems of strings with high mutual complexity
• Generating Kolmogorov random strings from sources with limited independence
• Symmetry of Information: A Closer Look
• scientific article; zbMATH DE number 3861050 (Why is no real title available?)
• Sets of K-independent strings
• Monotone complexity of a pair
• On generating independent random strings
• Counting Dependent and Independent Strings

This page was built for publication: Counting dependent and independent strings

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