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

DOI10.1007/978-3-031-20350-3_27arXiv2305.06570OpenAlexW4313349233MaRDI QIDQ6111971

Satyadev Nandakumar, Subin Pulari, Akhil S

Publication date: 4 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2305.06570

zbMATH Keywords

van Lambalgen's theoremfinite-state relative dimensionWall's theorem on the normality of AP subsequences

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Subsequences of normal sequences
• Entropy rates and finite-state dimension
• Finite-state independence
• Uniform van Lambalgen's theorem fails for computable randomness
• Towards a sharp converse of Wall's theorem on arithmetic progressions
• Endliche Automaten und Zufallsfolgen
• On Resource-Bounded Versions of the van Lambalgen Theorem
• Algorithmic Randomness and Complexity
• When van Lambalgen’s Theorem fails
• Von Mises' definition of random sequences reconsidered
• Ergodic Theorems and Converses for PSPACE Functions

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