





















The complexity of an infinite word can be measured in several ways, the two most common measures being the subword complexity and the abelian complexity. In 2015, Rigo and Salimov introduced a family of intermediate complexities indexed by $k\in\mathbb{N}_{>0}$: the $k$-binomial complexities. These complexities scale up from the abelian complexity, with which the $1$-binomial complexity coincides, to the subword complexity, to which they converge pointwise as $k$ tends to $+\infty$. In this article, we provide four classes of $d$-ary infinite words -- namely, $d$-ary $1$-balanced words, words with subword complexity $n\in\mathbb{N}_{>0}\mapsto n+(d-1)$ (which form a subclass of the so-called quasi-Sturmian words), hypercubic billiard words, and words constructed by repeated Sturmian colorings -- for which this scale ``collapses'', that is, all $k$-binomial complexities, for $k\geq 2$, coincide with the subword complexity. This work generalizes a result of Rigo and Salimov, established in their seminal paper from 2015, which asserts that the $k$-binomial complexity of any Sturmian word coincides with its subword complexity whenever $k\geq 2$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。