Abstract:
We show that the classical Hausdorff and constructive dimensions of any union of Π⁰₁ -definable sets of binary sequences are equal. If the union is effective, that is, the set of sequences is Σ⁰₂-definable, then the computable dimension also equals the Hausdorff dimension. This second result is implicit in the work of Staiger (1998). Staiger also proved related results using entropy rates of decidable languages. We show that Staiger's computable entropy rate provides an equivalent definition of computable dimension. We also prove that a constructive version of Staiger's entropy rate coincides with constructive dimension.

Journal Version:

• Theory of Computing Systems, 38(5):559-571, 2005.
  [PostScript | PDF | DOI link]

• Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (Malaga, Spain, July 8-13, 2002), Lecture Notes in Computer Science 2380, pages 561-571. Springer-Verlag, 2002.
  [Publisher's Page]