On Oscillation-free ε-random Sequences

DOI10.1016/J.ENTCS.2008.12.024zbMath1262.03070OpenAlexW1970982327MaRDI QIDQ4918022

Ludwig Staiger

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.024

zbMATH Keywords

\(\omega\)-wordspartial randomnessprefix complexitya priori complexityoscillation-free infinite words

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32)

Related Items (4)

On Oscillation-Free Chaitin h-Random Sequences ⋮ Exact constructive and computable dimensions ⋮ Constructive Dimension and Hausdorff Dimension: The Case of Exact Dimension ⋮ Finite state incompressible infinite sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constructive dimension equals Kolmogorov complexity
• The extent and density of sequences within the minimal-program complexity hierarchies
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• The dimensions of individual strings and sequences
• Kolmogorov complexity and Hausdorff dimension
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• On partial randomness
• Can an individual sequence of zeros and ones be random?
• A Theory of Program Size Formally Identical to Information Theory
• Relations between varieties of kolmogorov complexities
• Refined Bounds on Kolmogorov Complexity for ω-Languages
• INFINITE ITERATED FUNCTION SYSTEMS IN CANTOR SPACE AND THE HAUSDORFF MEASURE OF ω-POWER LANGUAGES
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences

This page was built for publication: On Oscillation-free ε-random Sequences