Kolmogorov-Loveland stochasticity for finite strings

DOI10.1016/J.IPL.2004.05.014MaRDI QIDQ2390324zbMATH OpenOpenAlexFDO

Authors Bruno Durand, Nikolai K. Vereshchagin

Publication date 21 July 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2004.05.014

zbMATH Keywords

algorithmsfinite stringKolmogorov-Loveland selection

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Foundations of probability theory (60A99)

Recommendations

• The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences
• Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity
• Kolmogorov-Loveland stochasticity and Kolmogorov complexity
• Kolmogorov-Loveland randomness and stochasticity
• scientific article; zbMATH DE number 4071998

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• Mathematical metaphysics of randomness
• On tables of random numbers
• Process complexity and effective random tests
• Some Properties of Kolmogorov $\Delta$-Random Finite Sequences
• The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences
• The definition of random sequences

Cited in

(14)

• What can be efficiently reduced to the Kolmogorov-random strings?
• scientific article; zbMATH DE number 5023089 (Why is no real title available?)
• A stochastic string with a compound Poisson process
• scientific article; zbMATH DE number 2086638 (Why is no real title available?)
• Grammatical Inference: Algorithms and Applications
• Bound on the cardinality of a covering of an arbitrary randomness test by frequency tests
• An excursion to the Kolmogorov random strings
• Deviations from uniformity in random strings
• An empirical study of the complexity and randomness of prediction error sequences
• Stabilization time for a type of evolution on binary strings
• The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences
• On the role of the law of large numbers in the theory of randomness
• Kolmogorov-Loveland stochasticity and Kolmogorov complexity
• Randomness deficiencies

This page was built for publication: Kolmogorov-Loveland stochasticity for finite strings

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