论文标题
关于斯特里亚语单词的谎言复杂性
On the Lie complexity of Sturmian words
论文作者
论文摘要
Bell and Shallit最近引入了无限单词$ s $的谎言复杂性，作为每个长度的功能计数的单词元素的数量，其元素都是$ s $的因素。他们证明，使用代数技术证明，谎言复杂性在上面是因子复杂性加一个的第一个区别。因此，它对于具有线性因子复杂性的单词统一，尤其是sturmian单词最多是2，这恰恰是每个$ n $的因子复杂性$ n+1 $的单词。在本说明中，我们提供了贝尔的结果的基本组合证明，并为任何斯特里亚语单词的谎言复杂性提供了确切的公式。
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.
