Finite-state dimension
From MaRDI portal
Bounded-depth circuitFinite-state compressorFinite-state dimensionFinite-state gamblerGaleHausdorff dimensionInformation-lossless compressorMartingaleNormal sequence
Fractals (28A80) Dimension theory of smooth dynamical systems (37C45) Martingales with discrete parameter (60G42) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)
Recommendations
Cites work
- A Mathematical Theory of Communication
- A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
- Algorithmic approach to the prediction problem
- Coding theorems for individual sequences
- Compression of individual sequences via variable-rate coding
- Dimension in Complexity Classes
- Endliche Automaten und Zufallsfolgen
- scientific article; zbMATH DE number 3941840 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- scientific article; zbMATH DE number 3566760 (Why is no real title available?)
- scientific article; zbMATH DE number 1142309 (Why is no real title available?)
- scientific article; zbMATH DE number 3227613 (Why is no real title available?)
- scientific article; zbMATH DE number 3328721 (Why is no real title available?)
- Kolmogorov complexity and Hausdorff dimension
- Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
- Normal numbers and sources for BPP
- On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
- The complexity and effectiveness of prediction algorithms
- The dimensions of individual strings and sequences
- THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES
Cited in
(49)- Dimension extractors and optimal decompression
- Computability theory. Abstracts from the workshop held January 7--13, 2018
- Prediction and dimension
- Finite-state independence
- Effective Hausdorff dimension in general metric spaces
- Dimension is compression
- Preservation of normality by non-oblivious group selection
- Computing absolutely normal numbers in nearly linear time
- Preservation of normality by transducers
- Two characterizations of finite-state dimension
- Normality and two-way automata
- Dimensions of Copeland-Erdös sequences
- Finite-state independence and normal sequences
- Base invariance of feasible dimension
- Generic density and small span theorem
- Dimension, entropy rates, and compression
- Finite state incompressible infinite sequences
- Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
- Cubic finite state machine
- Normality and finite-state dimension of Liouville numbers
- Bounded pushdown dimension vs Lempel Ziv information density
- On the difference between finite-state and pushdown depth
- Effective Dimensions and Relative Frequencies
- ALGORITHMS FOR FRACTAL DIMENSION CALCULATION
- A divergence formula for randomness and dimension
- Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression
- scientific article; zbMATH DE number 1754653 (Why is no real title available?)
- Normal numbers and computer science
- Finite self-information
- Normality and automata
- Algorithmic Fractal Dimensions in Geometric Measure Theory
- Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Pushdown and Lempel-Ziv depth
- A divergence formula for randomness and dimension
- Effective dimensions and relative frequencies
- Pebble-depth
- Deterministic pushdown automata can compress some normal sequences
- Local dynamical entropies and their applications in number theory
- A point to set principle for finite-state dimension
- Real numbers equally compressible in every base
- Normality, relativization, and randomness
- Are prime numbers and quadratic residues random?
- On normality in shifts of finite type
- Entropy rates and finite-state dimension
- A normal sequence compressed by PPM* but not by Lempel-Ziv 78
- Martingale families and dimension in P
- Complex network dimension and path counts
- Pushdown dimension
This page was built for publication: Finite-state dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1884962)
