Abstract:
It has been shown (see [10]), that there are strongly MARTIN-L¨O F-
ε–random w-words that behave in terms of complexity like random w-
words. That is, in particular, the a priori complexity of these ε–random
w-words is bounded from below and above by linear functions with
the same slope ε–. In this paper we will study the set of these w-words
in terms of HAUSDORFF measure and dimension.
Additionally we find upper bounds on a priori complexity, monotone
and simple complexity for a certain class of w-power languages.