Results for query **Staiger**:

__
TR06-070
| 23rd May 2006
__

Ludwig Staiger#### The Kolmogorov complexity of infinite words

__
TR16-139
| 8th September 2016
__

Ludwig Staiger#### Exact constructive and computable dimensions

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

__
TR16-013
| 12th January 2016
__

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

Revisions: 1

Ludwig Staiger

We present a brief survey of results on relations between the Kolmogorov

complexity of infinite strings and several measures of information content

(dimensions) known from dimension theory, information theory or fractal

geometry.

Special emphasis is laid on bounds on the complexity of strings in

more >>>

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

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