Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with finite-state dimension:
TR05-089 | 30th July 2005
Xiaoyang Gu, Jack H. Lutz, Philippe Moser

Dimensions of Copeland-Erdos Sequences

The base-$k$ {\em Copeland-Erd\"os sequence} given by an infinite
set $A$ of positive integers is the infinite
sequence $\CE_k(A)$ formed by concatenating the base-$k$
representations of the elements of $A$ in numerical
order. This paper concerns the following four
The {\em finite-state dimension} $\dimfs (\CE_k(A))$,
a finite-state ... more >>>

TR06-038 | 10th February 2006
David Doty, Jack H. Lutz, Satyadev Nandakumar

Finite-State Dimension and Real Arithmetic

We use entropy rates and Schur concavity to prove that, for every integer k >= 2, every nonzero rational number q, and every real number alpha, the base-k expansions of alpha, q+alpha, and q*alpha all have the same finite-state dimension and the same finite-state strong dimension. This extends, and gives ... more >>>

TR08-106 | 12th November 2008
Jack H. Lutz

A Divergence Formula for Randomness and Dimension

If $S$ is an infinite sequence over a finite alphabet $\Sigma$ and $\beta$ is a probability measure on $\Sigma$, then the {\it dimension} of $ S$ with respect to $\beta$, written $\dim^\beta(S)$, is a constructive version of Billingsley dimension that coincides with the (constructive Hausdorff) dimension $\dim(S)$ when $\beta$ is ... more >>>

ISSN 1433-8092 | Imprint