• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

Two Characterizations of Finite-State Dimension

P. 80-94.
Kozachinskiy A., Shen A.

In this paper we provide two equivalent characterizations of the notion of finite-state dimension introduced by Dai, Lathrop, Lutz and Mayordomo [7]. One of them uses Shannon’s entropy of non-aligned blocks and generalizes old results of Pillai [12] and Niven – Zuckerman [11]. The second characterizes finite-state dimension in terms of superadditive functions that satisfy some calibration condition (in particular, superadditive upper bounds for Kolmogorov complexity). The use of superadditive bounds allows us to prove a general sufficient condition for normality that easily implies old results of Champernowne [5], Besicovitch [1], Copeland and Erdös [6], and also a recent result of Calude, Staiger and Stephan [4].