2024/06/26 by Verónica Becher, Olivier Carton, Becher, Verónica +3 · 1 citation
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Information Theory (cs.IT) #Rings, Modules, and Algebras
paper · pdf · doi:10.48550/arxiv.2406.18383
openalex publication_date 2024/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
In 1976, Rauzy studied two complexity functions, \underlineβ and β, for infinite sequences over a finite alphabet. The function \underlineβ achieves its maximum precisely for Borel normal sequences, while β reaches its minimum for sequences that, when added to any Borel normal sequence, result in another Borel normal sequence. We establish a connection between Rauzy's complexity functions, \underlineβ and β, and the notions of non-aligned block entropy, \underlineh and h, by providing sharp upper and lower bounds for \underlineh in terms of \underlineβ, and sharp upper and lower bounds for h in terms of β. We adopt a probabilistic approach by considering an infinite sequence of random variables over a finite alphabet. The proof relies on a new characterization of non-aligned block entropies, h and \underlineh, in terms of Shannon's conditional entropy. The bounds imply that sequences with h = 0 coincide with those for which β = 0. We also show that the non-aligned block entropies, \underlineh and h, are essentially subadditive.