Counting dependent and independent strings

Details Counting dependent and independent strings Counting dependent and independent strings

2010-06-07

arxiv.org/abs/1006.1315v1

Computer Science

Computational Complexity

Scientific paper

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].

Affiliated with

Also associated with

No associations

Rating

Counting dependent and independent strings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting dependent and independent strings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting dependent and independent strings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-367770