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 metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02337412
Contributor : Alexander Shen <>
Submitted on : Tuesday, October 29, 2019 - 2:18:39 PM
Last modification on : Friday, November 8, 2019 - 3:48:02 PM
Long-term archiving on: : Thursday, January 30, 2020 - 6:11:33 PM

File

final-submitted-to-fct.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

77

Files downloads

105