Where should I learn about Kolmogorov complexity of overlapping substrings? I would like to know more about the relationship between the Kolmogorov complexity of a string and that of its substrings.  The relation that up to an additive constant, $K(x,y) = K(x) + K(y\ |\ x, K(x))$ begins to address this issue, but I am hoping there are results on substring complexity as opposed to the complexity of pairs of strings.  For example, suppose that it is possible to "cover" an infinite binary sequence $X$ with (possibly overlapping, possibly length-bounded) substrings $\sigma$ such that each $\sigma$ has $K(\sigma) < s|\sigma|$ (with $s$ being some fixed constant).  What can be said, if anything, about $K(\sigma)$ for arbitrary substrings $\sigma$ of $X$?  While an answer to that specific question is interesting if you have it, I am most hoping for pointers on where to learn about substring complexity more generally.
 A: Although I don't have the references you seek, I did notice that the following observation answers your specific question, in the case you don't impose any bound on the covering substrings. 
Claim. There is an infinite binary string $X$, which is covered by non-overlapping substrings $\sigma$, with $K(\sigma)\lt \frac12|\sigma|$, or indeed less than $s|\sigma|$ for any fixed desired $s$, such that every finite string arises infinitely often as a substring of $X$. 
The idea is simply to build $X$ as the concatenation of strings of the form $\sigma=\tau^\frown0000\cdots000$, where an arbitrary string $\tau$ is simply padded with an enormous number of $0$s so as to ensure $K(\sigma)$ is small in comparison with $|\sigma|$. Each such string has low complexity compared with its length. Consequently, if we construct $X$ as the concatenation of all such strings arising with all possible finite binary strings $\tau$, then $X$ will satisfy your covering property, but it will exhibit every possible finite string as a substring. 
In particular, we cannot deduce anything special about $K(\sigma)$ for an arbitrary substring of $X$ under the circumstances you describe, since every finite string is a substring of $X$.
In this example, the covering strings get longer and longer, but a similar argument works 
even when you impose a bound on the lengths. 
Claim. For any fixed even length $k$, there is an infinite binary string $X$ that is covered by non-overlapping finite strings $\sigma$ of length at most $k$, such that $K(\sigma)\leq\frac12|\sigma|+1$, such that every string of length $k$ arises as a substring of $X$. 
Build $X$ as the concatenation of all possible strings $\sigma$ of the form $$\tau^\frown000\cdots000\qquad\text{ or }\qquad000\cdots000^\frown\tau,$$ 
where the string $\tau$ is half of the string and the rest is made of $0$s. Any such string has $K(\sigma)\leq \frac12|\sigma|+1$, since you can just specify $\tau$ and then indicate whether the $0$s come before or after. But now the point is that if you build $X$ by sometimes putting the zeros first and sometimes by putting them last, then you can arrange that every possible string $\eta$ of length $k$ arises as a substring of $X$, since if $\eta=\eta_0^\frown\eta_1$ is cut in half, then $000\cdots000^\frown\eta_0^\frown\eta_1^\frown000\cdots000$ arises as a substring of $X$, where $\eta_0$ appears as the end of the first half and $\eta_1$ arises as the beginning of the next part. 
A: I cannot answer your specific question, but will just mention that
Ming Li and Paul Vitányi's great book is now it its 3rd edition
(Springer link):
     
