The Kolmogorov complexity function of an infinite word $\xi$ maps a natural
number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We
investigate the maximally achievable complexity function if $\xi$ is taken
from a constructively describable set of infinite words. Here we are
interested in linear upper bounds where the slope is the Hausdorff
dimension of the set.
As sets we consider $\Pi_{1}$-definable sets obtained by dilution and sets
obtained from constructively describable infinite iterated function
systems. In these cases, for a priori and monotone complexity, the upper
bound coincides (up to an additive constant) with the lower bound, thus
verifying the existence of oscillation-free maximally complex infinite words.
Proposition 5 and Equation (13) corrected
some typos corrected
The Kolmogorov complexity function of an infinite word $\xi$ maps a natural
number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We
investigate the maximally achievable complexity function if $\xi$ is taken
from a constructively describable set of infinite words. Here we are
interested in linear upper bounds where the slope is the Hausdorff
dimension of the set.
As sets we consider $\Pi_{1}$-definable sets obtained by dilution and sets
obtained from constructively describable infinite iterated function
systems. In these cases, for a priori and monotone complexity, the upper
bound coincides (up to an additive constant) with the lower bound, thus
verifying the existence of oscillation-free maximally complex infinite
correction of some typos
The Kolmogorov complexity function of an infinite word $\xi$ maps a natural
number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We
investigate the maximally achievable complexity function if $\xi$ is taken
from a constructively describable set of infinite words. Here we are
interested in linear upper bounds where the slope is the Hausdorff
dimension of the set.
As sets we consider $\Pi_{1}$-definable sets obtained by dilution and sets
obtained from constructively describable infinite iterated function
systems. In these cases, for a priori and monotone complexity, the upper
bound coincides (up to an additive constant) with the lower bound, thus
verifying the existence of oscillation-free maximally complex infinite
