Refined Bounds on Kolmogorov Complexity for ω-Languages

DOI10.1016/J.ENTCS.2008.12.016MaRDI QIDQ4918014zbMATH OpenOpenAlexFDO

Authors 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) Automata and formal grammars in connection with logical questions (03D05) Hausdorff and packing measures (28A78) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• scientific article; zbMATH DE number 3988704
• Kolmogorov Complexity and Deterministic Context-Free Languages
• On Languages with Very High Space-Bounded Kolmogorov Complexity
• Complexity of topological properties of regular \(\omega\)-languages
• Complexity of Topological Properties of Regular ω-Languages
• scientific article; zbMATH DE number 4043282
• \(\omega \)-rational languages: high complexity classes vs. Borel hierarchy
• The determinacy strength of pushdownω-languages
• Resource-bounded Kolmogorov complexity revisited
• Resource-bounded Kolmogorov complexity revisited

Cites work

• scientific article; zbMATH DE number 44693 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 3324894 (Why is no real title available?)
• scientific article; zbMATH DE number 2216397 (Why is no real title available?)
• Fractals, dimension, and formal languages
• Kolmogorov complexity and Hausdorff dimension
• On partial randomness
• 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

Cited in

(9)

• The determinacy strength of pushdownω-languages
• Exact constructive and computable dimensions
• Liouville, computable, Borel normal and Martin-Löf random numbers
• Two theorems on the Hausdorff measure of regular \(\omega\)-languages
• A Correspondence Principle for Exact Constructive Dimension
• On oscillation-free \(\varepsilon\)-random sequences
• Borel ranks and Wadge degrees of context free $\omega$-languages
• Constructive dimension and Hausdorff dimension: the case of exact dimension
• Bounds on the Kolmogorov complexity function for infinite words

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4918014)