Algorithmic complexity of β-expansions and application to A/D conversion

2024/05/06 by Valentin Abadie, Abadie, Valentin, Helmut Boelcskei +1
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · pdf · doi:10.48550/arxiv.2405.03816

openalex publication_date 2024/05/06 · openalex created_date 2024/05/11 · openalex updated_date 2026/07/30

Abstract

We establish diverse relationships between the algorithmic (Kolmogorov) complexity of the prefixes of any binary expansion and β-expansions. These relationships allow to develop intuitions on the complexity behavior of β-expansions, and raise problems related to compressibility of binary sequences generated in the context of A/D conversion relying on β-expansions. Our last contribution is to solve these problems.

Related

• Universal β-expansions
• Algebraic dependence in generating functions and expansion complexity
• On the expansion complexity of sequences over finite fields
• Transformations generating negative β-expansions
• An additively optimal interpreter for approximating Kolmogorov prefix complexity