Finite-state dimension and real arithmetic

DOI10.1016/j.ic.2007.05.003zbMath1130.68068arXivcs/0602032OpenAlexW2154904467MaRDI QIDQ2461795

David Doty, Jack H. Lutz, Satyadev Nandakumar

Publication date: 21 November 2007

Published in: Information and Computation, Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0602032

zbMATH Keywords

Schur concavityentropy rates

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Measures of information, entropy (94A17)

Related Items

STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY ⋮ Normality preserving operations for Cantor series expansions and associated fractals. I ⋮ Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ Functions that preserve p-randomness ⋮ Non-trivial matrix actions preserve normality for continued fractions ⋮ Some complexity results in the theory of normal numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subsequences of normal sequences
• On normal numbers
• Entropy rates and finite-state dimension
• Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
• Normal numbers and selection rules
• Fractal dimension and logarithmic loss unpredictability.
• Finite-state dimension
• The dimensions of individual strings and sequences
• Dimensions of Copeland-Erdös sequences
• Selection functions that do not preserve normality
• Endliche Automaten und Zufallsfolgen
• On a problem of Steinhaus about normal numbers
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Two definitions of fractional dimension
• Dimension in Complexity Classes
• The Construction of Decimals Normal in the Scale of Ten
• Inequalities: theory of majorization and its applications