|
Construction of Sequences of Zeros and Ones with Complex Finite Sequences / Rumyantsev A.Yu. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2010. № 1. P. 41-45 [Moscow Univ. Math. Bulletin. Vol. 65, No 1, 2010. P. 39-43]. We construct infinite sequences of zeros and ones under some restrictions (not to contain subwords of some definite type or definite bits at definite positions, etc.). This paper concerns probabilistic methods of constructing such sequences with application of the Lovász lemma and their reformulation in terms of the Kolmogorov complexity and Martin-Löf randomness.
Key words: Kolmogorov complexity, prefix complexity,
sequence, subsequence, combinatorics, probability.
|