Entropy rates and finite-state dimension

DOI10.1016/j.tcs.2005.09.040zbMath1085.37017OpenAlexW2043927415WikidataQ56158170 ScholiaQ56158170MaRDI QIDQ817815

N. V. Vinodchandran, John M. Hitchcock, Chris Bourke

Publication date: 20 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.040

zbMATH Keywords

regular languagesgenericityfinite-state dimensionnormal sequences

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Fractals (28A80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Dimension theory of smooth dynamical systems (37C45)

Related Items

Normality and finite-state dimension of Liouville numbers ⋮ STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY ⋮ Dimensions of Copeland-Erdös sequences ⋮ Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ Functions that preserve p-randomness ⋮ A divergence formula for randomness and dimension ⋮ Finite-state relative dimension, dimensions of AP subsequences and a finite-state van Lambalgen's theorem ⋮ Bounded Pushdown Dimension vs Lempel Ziv Information Density ⋮ Base invariance of feasible dimension ⋮ Finite-state dimension and real arithmetic ⋮ Finite state complexity ⋮ Pushdown dimension ⋮ Computing absolutely normal numbers in nearly linear time ⋮ Dimension extractors and optimal decompression ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory ⋮ Finite state incompressible infinite sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correspondence principles for effective dimensions
• Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
• Subword complexities of various classes of deterministic developmental languages without interactions
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Fractal dimension and logarithmic loss unpredictability.
• Generalization of automatic sequences for numeration systems on a regular language
• Finite-state dimension
• The dimensions of individual strings and sequences
• Kolmogorov complexity and Hausdorff dimension
• Endliche Automaten und Zufallsfolgen
• Finite state languages
• Two definitions of fractional dimension
• Compression of individual sequences via variable-rate coding
• Dimension in Complexity Classes
• STACS 2004
• On the entropy of context-free languages
• Uniform tag sequences