二元字母表上光滑词的复杂度
The complexity of smooth words over binary alphabets
Julien Cassaigne, Raphaël Henry
AI 速读 基于摘要
该论文研究二元字母表上光滑词与光滑序列的关系，并在复杂度猜想上取得进展：证明任意字母表的下界、偶数字母表的上界，并改进奇数与混合字母表的上界。
cs.FL · math.CO · math.DS
查看原文摘要
Smooth sequences over an alphabet of positive integers $\{a,b\}$ are sequences that are infinitely derivable, the emblematic example being the Oldenburger-Kolakoski sequence $κ$ over $\{1,2\}$. The main way to study their language is to consider a finite version of smooth sequences called smooth words. In this paper we prove that the smooth words are exactly the factors of smooth sequences and we make progress towards the conjecture that the complexity of smooth words over $\{a,b\}$ grows like $Θ\left(n^{\log(a+b)/\log((a+b)/2)}\right)$: we prove the lower bound over any alphabet and the upper bound over even alphabets, and we improve the known upper bound over odd and mixed alphabets. We also provide a dichotomy that links the language, the morphicity and the factor complexity of $κ$.