Finite-state relative dimension, dimensions of A. P. subsequences and a finite-state van Lambalgen's theorem

DOI10.1016/J.IC.2024.105156MaRDI QIDQ6543262zbMATH OpenFDO

Authors S. Nandakumar, Subin Pulari, Akhil S

Publication date 24 May 2024

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

zbMATH Keywords

van Lambalgen's theoremfinite-state relative dimensionWall's theorem on the normality of A. P. subsequences

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 1754653 (Why is no real title available?)
• Algorithmic randomness and complexity.
• Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
• Endliche Automaten und Zufallsfolgen
• Entropy rates and finite-state dimension
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• Finite-state independence
• Higher order concentration for functions of weakly dependent random variables
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On Resource-Bounded Versions of the van Lambalgen Theorem
• Subsequences of normal sequences
• Towards a sharp converse of Wall's theorem on arithmetic progressions
• Two characterizations of finite-state dimension
• Uniform van Lambalgen's theorem fails for computable randomness
• When van Lambalgen’s Theorem fails

This page was built for publication: Finite-state relative dimension, dimensions of A. P. subsequences and a finite-state van Lambalgen's theorem

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