Skip to Main content Skip to Navigation
Conference papers

Two Characterizations of Finite-State Dimension

Abstract : In this paper we provide two equivalent characterizations of the notion of finite-state dimension introduced by Dai, Lathrop, Lutz and Mayordomo (2004). One of them uses Shannon's entropy of non-aligned blocks and generalizes old results of Pillai (1940) and Niven-Zuckerman (1951). 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 (1933), Besicovitch (1935), Copeland and Erdös (1946), and also a recent result of Calude, Staiger and Stephan (2016).
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Alexander Shen <>
Submitted on : Tuesday, October 29, 2019 - 2:18:39 PM
Last modification on : Friday, May 21, 2021 - 8:22:02 PM
Long-term archiving on: : Thursday, January 30, 2020 - 6:11:33 PM


Files produced by the author(s)




Alexander Kozachinskiy, Alexander Shen. Two Characterizations of Finite-State Dimension. FCT: Fundamentals of Computation Theory, Aug 2019, Copenhagen, Denmark. pp.80-94, ⟨10.1007/978-3-030-25027-0_6⟩. ⟨lirmm-02337412⟩



Record views


Files downloads