Cyclic complexity of words

详细信息    查看全文

• 作者：Julien Cassaigne^a ; ^{julien.cassaigne@math.cnrs.fr" class="auth_mail" title="E-mail the corresponding author} ; Gabriele Fici^b ; ^{gabriele.fici@unipa.it" class="auth_mail" title="E-mail the corresponding author} ; Marinella Sciortino^b ; ^{marinella.sciortino@unipa.it" class="auth_mail" title="E-mail the corresponding author} ; Luca Q. Zamboni^c ; ^{zamboni@math.univ-lyon1.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Cyclic complexity ; Factor complexity ; Sturmian words
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：145
• 期：Complete
• 页码：36-56
• 全文大小：470 K

文摘

We introduce and study a complexity function on words c_x(n)$c_x(n)$, called cyclic complexity, which counts the number of conjugacy classes of factors of length n of an infinite word x. We extend the well-known Morse–Hedlund theorem to the setting of cyclic complexity by showing that a word is ultimately periodic if and only if it has bounded cyclic complexity. Unlike most complexity functions, cyclic complexity distinguishes between Sturmian words of different slopes. We prove that if x is a Sturmian word and y is a word having the same cyclic complexity of x, then up to renaming letters, x and y have the same set of factors. In particular, y is also Sturmian of slope equal to that of x  . Since c_x(n)=1$c_x(n)=1$ for some aafe4a2b" title="Click to view the MathML source">n≥1$n\ge 1$ implies x   is periodic, it is natural to consider the quantity ${\lim \inf }_{n\to \infty }{c}_x(n)$. We show that if x   is a Sturmian word, then ${\lim \inf }_{n\to \infty }{c}_x(n)=2$. We prove however that this is not a characterization of Sturmian words by exhibiting a restricted class of Toeplitz words, including the period-doubling word, which also verify this same condition on the limit infimum. In contrast we show that, for the Thue–Morse word t  , ${\lim \inf }_{n\to \infty }{c}_t(n)=+\infty$.