SETS OF K-INDEPENDENT STRINGS

被引：1

作者：

Ti, Yen-Wu ^{[3
]}

Chang, Ching-Lueh ^{[2
]}

Lyuu, Yuh-Dauh ^{[1
,4
]}

Shen, Alexander ^{[5
,6
,7
]}

机构：

[1] Natl Taiwan Univ, Dept Comp Sci & Informat Engn, Taipei 106, Taiwan

[2] Natl Taiwan Univ, Dept Comp Sci & Informat Engn, Taipei 10764, Taiwan

[3] Hwa Hsia Inst Technol, Dept Comp Sci Informat & Engn, Taipei, Taiwan

[4] Natl Taiwan Univ, Dept Finance, Taipei 106, Taiwan

[5] CNRS, Lab Informat Fondamentale, Marseille, France

[6] Univ Aix Marseille, Marseille, France

[7] IITP RAS, Moscow, Russia

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2010年 / 21卷 / 03期

关键词：

Kolmogorov complexity; k-independent string;

D O I：

10.1142/S0129054110007271

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A bit string is random (in the sense of algorithmic information theory) if it is incompressible, i.e., its Kolmogorov complexity is close to its length. Two random strings are independent if knowing one of them does not simplify the description of the other, i.e., the conditional complexity of each string (using the other as a condition) is close to its length. We may define independence of a k-tuple of strings in the same way. In this paper we address the following question: what is that maximal cardinality of a set of n-bit strings if any k elements of this set are independent (up to a certain constant)? Lower and upper bounds that match each other (with logarithmic precision) are provided.

引用

页码：321 / 327

页数：7