Refined Bounds on Kolmogorov Complexity for ω-Languages
DOI10.1016/J.ENTCS.2008.12.016zbMATH Open1262.68056OpenAlexW1967356049MaRDI QIDQ4918014FDOQ4918014
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
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Kolmogorov complexity and Hausdorff dimension
- On partial randomness
- Title not available (Why is that?)
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- Relations between varieties of kolmogorov complexities
- Title not available (Why is that?)
- Fractals, dimension, and formal languages
Cited In (9)
- A Correspondence Principle for Exact Constructive Dimension
- Liouville, computable, Borel normal and Martin-Löf random numbers
- The determinacy strength of pushdownω-languages
- Borel ranks and Wadge degrees of context free $\omega$-languages
- Bounds on the Kolmogorov complexity function for infinite words
- On oscillation-free \(\varepsilon\)-random sequences
- Two theorems on the Hausdorff measure of regular \(\omega\)-languages
- Exact constructive and computable dimensions
- Constructive dimension and Hausdorff dimension: the case of exact dimension
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)
