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.