Two Characterizations of Finite-State Dimension - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Two Characterizations of Finite-State Dimension

Résumé

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).
Fichier principal
Vignette du fichier
final-submitted-to-fct.pdf (315.99 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-02337412 , version 1 (29-10-2019)

Identifiants

Citer

Alexander Kozachinskiy, Alexander Shen. Two Characterizations of Finite-State Dimension. FCT 2019 - 22nd International Symposium on Fundamentals of Computation Theory, Aug 2019, Copenhagen, Denmark. pp.80-94, ⟨10.1007/978-3-030-25027-0_6⟩. ⟨lirmm-02337412⟩
56 Consultations
155 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More