Refined Bounds on Kolmogorov Complexity for ω-Languages
From MaRDI portal
Publication:4918014
DOI10.1016/j.entcs.2008.12.016zbMath1262.68056MaRDI QIDQ4918014
Publication date: 3 May 2013
Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.entcs.2008.12.016
68Q45: Formal languages and automata
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
03D05: Automata and formal grammars in connection with logical questions
28A78: Hausdorff and packing measures
Related Items
On Oscillation-free ε-random Sequences, Exact constructive and computable dimensions, Liouville, computable, Borel normal and Martin-Löf random numbers, A Correspondence Principle for Exact Constructive Dimension, Constructive Dimension and Hausdorff Dimension: The Case of Exact Dimension
Cites Work
- Kolmogorov complexity and Hausdorff dimension
- On partial randomness
- Fractals, dimension, and formal languages
- Relations between varieties of kolmogorov complexities
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item