All reports by Author Ludwig Staiger:

__
TR16-139
| 8th September 2016
__

Ludwig Staiger#### Exact constructive and computable dimensions

Revisions: 1

__
TR16-013
| 12th January 2016
__

Ludwig Staiger#### Bounds on the Kolmogorov complexity function for infinite words

Revisions: 1

__
TR11-132
| 2nd September 2011
__

Ludwig Staiger#### Oscillation-free Chaitin $h$-random sequences

Revisions: 1

__
TR11-074
| 27th April 2011
__

Ludwig Staiger#### Exact constructive dimension

Revisions: 1

Ludwig Staiger

In this paper we derive several results which generalise the constructive

dimension of (sets of) infinite strings to the case of exact dimension. We

start with proving a martingale characterisation of exact Hausdorff

dimension. Then using semi-computable super-martingales we introduce the

notion of exact constructive dimension ...
more >>>

Ludwig Staiger

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 ...
more >>>

Ludwig Staiger

The present paper generalises results by Tadaki [12] and Calude et al. [1] on oscillation-free partially random infinite strings. Moreover, it shows that oscillation-free partial Chaitin randomness can be separated from scillation-free partial strong Martin-L\"of randomness by $\Pi_{1}^{0}$-definable sets of infinite strings.

more >>>Ludwig Staiger

The present paper generalises results by Lutz and Ryabko. We prove a

martingale characterisation of exact Hausdorff dimension. On this base we

introduce the notion of exact constructive dimension of (sets of) infinite

strings.

Furthermore, we generalise Ryabko's result on the Hausdorff dimension of the

...
more >>>