Bell and Shallit recently introduced the Lie complexity of an infinite word $s$ as the function counting for each length the number of conjugacy classes of words whose elements are all factors of $s$. They proved, using algebraic techniques, that the Lie complexity is bounded above by the first difference of the factor complexity plus one; hence, it is uniformly bounded for words with linear factor complexity, and, in particular, it is at most 2 for Sturmian words, which are precisely the words with factor complexity $n+1$ for every $n$. In this note, we provide an elementary combinatorial proof of the result of Bell and Shallit and give an exact formula for the Lie complexity of any Sturmian word.
翻译：Bell and Shalit最近引入了无限字数的复杂性。 字数是无限的字数, 以每长的字数计算。 它们用代数技术证明, 字数的复杂性比因素复杂度的第一个差异加一个, 因此, 字数与线性因素复杂度一致, 特别是, Sturmian 字数最多是两个, 也就是每美元中每个字的复数, 也就是每美元中具有要素复杂性的字数。 在本说明中, 我们提供了Bell 和 Shalit 的结果的基本组合证明, 并为任何Sturmian 字的精度复杂性给出了精确的公式 。
相关内容
微信扫码咨询专知VIP会员