Abstract:
The effective fractal dimensions at the polynomial-space level and
above can all be equivalently defined as the C-entropy rate
where C is the class of languages corresponding to the level of
effectivization. For example, pspace-dimension is equivalent to the
PSPACE-entropy rate.

At lower levels of complexity the equivalence proofs break down. In
the polynomial-time case, the P-entropy rate is a lower bound on
the p-dimension. Equality seems unlikely, but separating the
P-entropy rate from p-dimension would require proving P ≠ NP.

We show that at the finite-state level, the opposite of the
polynomial-time case happens: the REG-entropy rate is an upper
bound on the finite-state dimension. We also use the finite-state
genericity of Ambos-Spies and Busse (2003) to separate finite-state
dimension from the REG-entropy rate.

However, we point out that a block-entropy rate
characterization of finite-state dimension follows from the work of
Ziv and Lempel (1978) on finite-state compressibility and the
compressibility characterization of finite-state dimension by Dai,
Lathrop, Lutz, and Mayordomo (2004).

As applications of the REG-entropy rate upper bound and the
block-entropy rate characterization, we prove that every regular
language has finite-state dimension 0 and that normality is equivalent
to finite-state dimension 1.