An algorithm for the word entropy

Abstract

For any infinite word $w$ on a finite alphabet $A$, the complexity function $p_w$ of $w$ is the sequence counting, for each non-negative $n$, the number $p_w(n)$ of words of length $n$ on the alphabet $A$ that are factors of the infinite word $w$ and the the entropy of $w$ is the quantity $E(w)=\underset{n\to \infty }{\lim }\frac{1}{n}\log p_w(n)$. For any given function $f$ with exponential growth, Mauduit and Moreira introduced in [MM17] the notion of word entropy $E_W(f)=\sup \{E(w),w\in A^{\mathbb{N}},p_w\le f\}$ and showed its links with fractal dimensions of sets of infinite sequences with complexity function bounded by $f$. The goal of this work is to give an algorithm to estimate with arbitrary precision $E_W(f)$ from finitely many values of $f$.