Entropy rates and finite-state dimension

DOI10.1016/J.TCS.2005.09.040MaRDI QIDQ817815zbMATH OpenOpenAlexWikidataFDO

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

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

genericityfinite-state dimensionregular languagesnormal sequences

Mathematics Subject Classification ID

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

Recommendations

• Finite-state dimension
• Two characterizations of finite-state dimension
• scientific article; zbMATH DE number 1754653
• Dimension, entropy rates, and compression
• Effective Dimensions and Relative Frequencies

Cites work

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

Cited in

(18)

• Finite state incompressible infinite sequences
• A divergence formula for randomness and dimension
• Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
• Finite state complexity
• Normality and finite-state dimension of Liouville numbers
• Pushdown dimension
• Bounded pushdown dimension vs Lempel Ziv information density
• Finite-state dimension
• Dimension extractors and optimal decompression
• Algorithmic Fractal Dimensions in Geometric Measure Theory
• scientific article; zbMATH DE number 3932938 (Why is no real title available?)
• Computing absolutely normal numbers in nearly linear time
• State-size hierarchy for finite-state complexity
• Base invariance of feasible dimension
• Dimension, entropy rates, and compression
• Finite-state relative dimension, dimensions of AP subsequences and a finite-state van Lambalgen's theorem
• Dimensions of Copeland-Erdös sequences
• Finite-state relative dimension, dimensions of A. P. subsequences and a finite-state van Lambalgen's theorem

This page was built for publication: Entropy rates and finite-state dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817815)