The complexity of finite smooth words over binary alphabets
This work addresses a theoretical problem in combinatorics on words, specifically for researchers studying smooth words and their properties, and is incremental as it builds on existing conjectures and bounds.
The paper tackled the problem of characterizing finite smooth words (f-smooth words) and their complexity over binary alphabets, proving that f-smooth words are exactly the factors of smooth words and making progress on a conjecture about their growth rate, including proving the lower bound for any binary alphabet and improving the upper bound for odd alphabets.
Smooth words over an alphabet of non-negative integers $\{a,b\}$ are infinite words that are infinitely derivable, the most famous example being the Oldenburger-Kolakoski word over $\{1,2\}$. The main way to study their language is to consider a finite version of smooth words that we call f-smooth words. In this paper we prove that the f-smooth words are exactly the factors of smooth words, and we make progress towards the conjecture of Sing that the complexity of f-smooth words over $\{a,b\}$ grows like $Θ\left(n^{\log(a+b)/\log((a+b)/2)}\right)$: we prove it over even alphabets, we prove the lower bound over any binary alphabet and we improve the known upper bound over odd alphabets.