Automatic Kolmogorov complexity and normality revisited

Alexander Shen 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : It is well known that normality (all factors of given length appear in an infinite sequence with the same frequency) can be described as incompressibility via finite automata. Still the statement and proof of this result as given by Becher and Heiber [4] in terms of " lossless finite-state compressors " do not follow the standard scheme of Kolmogorov complexity definition (the automaton is used for compression, not decompression). We modify this approach to make it more similar to the traditional Kolmogorov complexity theory (and simpler) by explicitly defining the notion of automatic Kolmogorov complexity and using its simple properties. Other known notions (Shallit–Wang [9], Calude–Salomaa–Roblot [5]) of description complexity related to finite automata are discussed (see the last section). As a byproduct, we obtain simple proofs of classical results about normality (equivalence of definitions with aligned occurences and all occurencies, Wall's theorem saying that a normal number remains normal when multiplied by a rational number, and Agafonov's result saying that normality is preserved by automatic selection rules).
Type de document :
Chapitre d'ouvrage
Fundamentals of Computation Theory, 2017, Proceedings, 10472, Springer, pp.418-430, 2017, Lecture Notes in Computer Science, 978-3-662-55751-8. 〈10.1007/978-3-662-55751-8_33〉. 〈springer.com〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01486488
Contributeur : Alexander Shen <>
Soumis le : jeudi 9 mars 2017 - 20:50:49
Dernière modification le : mercredi 30 mai 2018 - 14:09:53

Lien texte intégral

Identifiants

Collections

Citation

Alexander Shen. Automatic Kolmogorov complexity and normality revisited. Fundamentals of Computation Theory, 2017, Proceedings, 10472, Springer, pp.418-430, 2017, Lecture Notes in Computer Science, 978-3-662-55751-8. 〈10.1007/978-3-662-55751-8_33〉. 〈springer.com〉. 〈lirmm-01486488〉

Partager

Métriques

Consultations de la notice

136