𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Kolmogorov complexity characterization of constructive Hausdorff dimension

✍ Scribed by Elvira Mayordomo

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
49 KB
Volume
84
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A characterization of constructive dimen
A characterization of constructive dimension
✍ Satyadev Nandakumar πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 173 KB

## Abstract In the context of Kolmogorov's algorithmic approach to the foundations of probability, Martin‐LΓΆf defined the concept of an individual random sequence using the concept of a constructive measure 1 set. Alternate characterizations use constructive martingales and measures of impossibilit

On hausdorff and topological dimensions
On hausdorff and topological dimensions of the kolmogorov complexity of the real line
✍ Jin-yi Cai; Juris Hartmanis πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 767 KB

We investigate the Kolmogorov complexity of real numbers. Let K be the Kolmogorov complexity function; we determine the Hausdorff dimension and the topological dimension of the graph of K. Since these dimensions are different, the graph of the Kolmogorov complexity function of the real line forms a

Construction of expanders and superconce
Construction of expanders and superconcentrators using Kolmogorov complexity
✍ Uwe SchΓΆning πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 140 KB

We show the existence of various versions of expander graphs using Kolmogorov complexity. This method seems superior to the usual probabilistic construction. It turns out that the best known bounds on the size of expanders and superconcentrators can be attained based on this method. In the case of (