Abstract:
We consider a new family of factorial languages whose subword complexity grows as $\Theta(n^\alpha)$, where $\alpha$ is the only positive root of some transcendental equation. The asymptotic growth of the complexity function of these languages is studied by discrete and analytical methods, a corollary of the Wiener–Pitt theorem inclusive. The factorial languages considered are also languages of arithmetical factors of infinite words; so, we describe a new family of infinite words with an unusual growth of arithmetical complexity.
Keywords:subword complexity, arithmetical complexity, combinatorics on words, Toeplitz words, asymptotic combinatorics, analytical methods in combinatorics, Tauberian theorems, Wiener–Pitt theorem.