Refined Bounds on Kolmogorov Complexity for ω-Languages

DOI10.1016/j.entcs.2008.12.016zbMath1262.68056OpenAlexW1967356049MaRDI QIDQ4918014

Jöran Mielke

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

zbMATH Keywords

measuresKolmogorov complexity\(\omega\)-languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Automata and formal grammars in connection with logical questions (03D05) Hausdorff and packing measures (28A78)

Related Items (5)

A Correspondence Principle for Exact Constructive Dimension ⋮ Exact constructive and computable dimensions ⋮ On Oscillation-free ε-random Sequences ⋮ Liouville, computable, Borel normal and Martin-Löf random numbers ⋮ 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

This page was built for publication: Refined Bounds on Kolmogorov Complexity for ω-Languages