Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity

zbMath0613.94006MaRDI QIDQ1820127

Boris Ya. Ryabko

Publication date: 1986

Published in: Problems of Information Transmission (Search for Journal in Brave)

zbMATH Keywords

Turing machinesKolmogorov complexityfinite automataquasi-entropycost of the optimal codenoiseless codingsources generated by formal grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Source coding (94A29)

Related Items (28)

Effective fractal dimensions ⋮ Finite-state dimension ⋮ Constructive dimension equals Kolmogorov complexity ⋮ The dimensions of individual strings and sequences ⋮ On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line ⋮ Partial Randomness and Dimension of Recursively Enumerable Reals ⋮ The Kolmogorov complexity of infinite words ⋮ Optimal redundancy in computations from random oracles ⋮ The Kučera-Gács theorem revisited by Levin ⋮ Exact constructive and computable dimensions ⋮ Spatial analysis of cities using Renyi entropy and fractal parameters ⋮ Dimension is compression ⋮ Fractal Intersections and Products via Algorithmic Dimension ⋮ Algorithmic information theory and its statistical mechanical interpretation ⋮ Generalised entropies and asymptotic complexities of languages ⋮ Error-correcting codes and phase transitions ⋮ Prediction and dimension ⋮ Liouville, computable, Borel normal and Martin-Löf random numbers ⋮ Effective Hausdorff dimension in general metric spaces ⋮ Constructive dimension and Turing degrees ⋮ A wave-spectrum analysis of urban population density: Entropy, fractal, and spatial localization ⋮ Scaled dimension and the Kolmogorov complexity of Turing-hard sets ⋮ Dimension extractors and optimal decompression ⋮ Equivalent relation between normalized spatial entropy and fractal dimension ⋮ Kolmogorov-Loveland randomness and stochasticity ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory ⋮ The Kolmogorov complexity of real numbers. ⋮ Finite state incompressible infinite sequences

This page was built for publication: Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity