Conditional normality and finite-state dimensions revisited

DOI10.1016/J.TCS.2025.115570MaRDI QIDQ6896765zbMATH OpenFDO

Authors A. Shen

Publication date 21 November 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115570

zbMATH Keywords

algorithmic information theoryBorel normalityconditional normalityfinite-state dimension

Mathematics Subject Classification ID

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

Review text

This paper establishes the equivalence of five different definitions of conditional finite-state dimension for binary infinite sequences: asymptotic block frequency, finite-state gambling, automatic complexity, superadditive complexity, and finite-state a priori complexity.\N\NWhile the equivalence of the block frequency and gambling approaches was the main result of [\textit{S. Nandakumar} et al., Inf. Comput. 298, Article ID 105156, 20 p. (2024; Zbl 07852925)], this paper demonstrates that these and other characterizations can be derived more simply and directly. It does so by extending classical equivalences from the unconditional theory of finite-state dimension to the conditional setting.

Cites work

• Around Kolmogorov complexity: basic notions and results
• Compression of individual sequences via variable-rate coding
• Kolmogorov Complexity and Algorithmic Randomness

This page was built for publication: Conditional normality and finite-state dimensions revisited

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