Finite-state dimension

DOI10.1016/S0304-3975(03)00244-5zbMath1071.68027WikidataQ60578980 ScholiaQ60578980MaRDI QIDQ1884962

James I. Lathrop, Jack Jie Dai, Jack H. Lutz, Elvira Mayordomo

Publication date: 27 October 2004

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

zbMATH Keywords

Hausdorff dimensionMartingaleBounded-depth circuitFinite-state compressorFinite-state dimensionFinite-state gamblerGaleInformation-lossless compressorNormal sequence

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Formal languages and automata (68Q45) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) 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 ⋮ A normal sequence compressed by PPM* but not by Lempel-Ziv 78 ⋮ Dimensions of Copeland-Erdös sequences ⋮ Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ A divergence formula for randomness and dimension ⋮ Pushdown and Lempel-Ziv depth ⋮ Finite-state independence and normal sequences ⋮ Effective Dimensions and Relative Frequencies ⋮ Dimension is compression ⋮ Bounded Pushdown Dimension vs Lempel Ziv Information Density ⋮ Normal Numbers and Computer Science ⋮ ALGORITHMS FOR FRACTAL DIMENSION CALCULATION ⋮ Base invariance of feasible dimension ⋮ Effective dimensions and relative frequencies ⋮ Martingale families and dimension in P ⋮ Computability theory. Abstracts from the workshop held January 7--13, 2018 ⋮ On the Difference Between Finite-State and Pushdown Depth ⋮ Finite-state dimension and real arithmetic ⋮ Normality and automata ⋮ Generic density and small span theorem ⋮ A Divergence Formula for Randomness and Dimension ⋮ Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable ⋮ Complex network dimension and path counts ⋮ Dimension, entropy rates, and compression ⋮ Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression ⋮ Prediction and dimension ⋮ Finite-state independence ⋮ Effective Hausdorff dimension in general metric spaces ⋮ Pushdown dimension ⋮ Preservation of normality by non-oblivious group selection ⋮ Computing absolutely normal numbers in nearly linear time ⋮ Dimension extractors and optimal decompression ⋮ Preservation of normality by transducers ⋮ On normality in shifts of finite type ⋮ Normality and two-way automata ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory ⋮ Finite state incompressible infinite sequences ⋮ Entropy rates and finite-state dimension

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Algorithmic approach to the prediction problem
• The complexity and effectiveness of prediction algorithms
• On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Normal numbers and sources for BPP
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• The dimensions of individual strings and sequences
• Kolmogorov complexity and Hausdorff dimension
• Endliche Automaten und Zufallsfolgen
• Coding theorems for individual sequences
• Compression of individual sequences via variable-rate coding
• Dimension in Complexity Classes
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES