Space-bounded online Kolmogorov complexity is additive

Bruno Bauwens, Maria Marchenko

The even online Kolmogorov complexity of a string $x=x_1{x}_2\cdots x_n$ is the minimal length of a program that for all $i\le n/2$, on input $x_1{x}_3\cdots x_{2i-1}$ outputs $…