Forbidden substrings, Kolmogorov complexity and almost periodic sequences

Details Forbidden substrings, Kolmogorov complexity and almost periodic sequences Forbidden substrings, Kolmogorov complexity and almost periodic sequences

2010-09-22

arxiv.org/abs/1009.4455v1

Andrey Yu. Rumyantsev, Maxim A. Ushakov, Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences, Springer,

Mathematics

Combinatorics

Scientific paper

Assume that for some $\alpha<1$ and for all nutural $n$ a set $F_n$ of at most $2^{\alpha n}$ "forbidden" binary strings of length $n$ is fixed. Then there exists an infinite binary sequence $\omega$ that does not have (long) forbidden substrings. We prove this combinatorial statement by translating it into a statement about Kolmogorov complexity and compare this proof with a combinatorial one based on Laslo Lovasz local lemma. Then we construct an almost periodic sequence with the same property (thus combines the results of Levin and Muchnik-Semenov-Ushakov). Both the combinatorial proof and Kolmogorov complexity argument can be generalized to the multidimensional case.

Affiliated with

Also associated with

No associations

Rating

Forbidden substrings, Kolmogorov complexity and almost periodic sequences 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 Forbidden substrings, Kolmogorov complexity and almost periodic sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Forbidden substrings, Kolmogorov complexity and almost periodic sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-638515