Finite state incompressible infinite sequences

DOI10.1016/j.ic.2015.11.003zbMath1338.68128OpenAlexW2234983666MaRDI QIDQ259039

Ludwig Staiger, Cristian S. Calude, Frank Stephan

Publication date: 10 March 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2015.11.003

zbMATH Keywords

normalityAITfinite state complexityfinite state incompressibility

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (3)

Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ Pushdown and Lempel-Ziv depth ⋮ On the Difference Between Finite-State and Pushdown Depth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Representation of left-computable \(\varepsilon \)-random reals
• Finite state complexity
• Entropy rates and finite-state dimension
• Constructive dimension equals Kolmogorov complexity
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• The Kolmogorov complexity of real numbers.
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• Finite-state dimension
• The dimensions of individual strings and sequences
• Process complexity and effective random tests
• Kolmogorov complexity and Hausdorff dimension
• The Kolmogorov complexity of infinite words
• Endliche Automaten und Zufallsfolgen
• On partial randomness
• An almost machine-independent theory of program-length complexity, sophistication, and induction
• STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY
• Phase Transition and Strong Predictability
• Algorithmic Randomness and Complexity
• Approximating the smallest grammar
• A Theory of Program Size Formally Identical to Information Theory
• Compression of individual sequences via variable-rate coding
• Complexity dips in random infinite binary sequences
• On Oscillation-free ε-random Sequences
• Resource-bounded kolmogorov complexity revisited
• Mathematical Foundations of Computer Science 2004
• Feasible Depth
• A computable absolutely normal Liouville number
• Complexity oscillations in infinite binary sequences
• 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
• An example of a computable absolutely normal number

This page was built for publication: Finite state incompressible infinite sequences