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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300553&_mathId=si1.gif&_user=111111111&_pii=S0097316516300553&_rdoc=1&_issn=00973165&md5=b76d61ad5897ca36df46de729c5f46c4" title="Click to view the MathML source">c_x(n)class="mathContainer hidden">class="mathCode">$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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300553&_mathId=si2.gif&_user=111111111&_pii=S0097316516300553&_rdoc=1&_issn=00973165&md5=dff7e88d420c28970b88dba875c23b6e" title="Click to view the MathML source">c_x(n)=1class="mathContainer hidden">class="mathCode">$c_x(n)=1$ for some class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300553&_mathId=si3.gif&_user=111111111&_pii=S0097316516300553&_rdoc=1&_issn=00973165&md5=b7eea330929eada231930a7eaafe4a2b" title="Click to view the MathML source">n≥1class="mathContainer hidden">class="mathCode">$n\ge 1$ implies x   is periodic, it is natural to consider the quantity class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300553&_mathId=si4.gif&_user=111111111&_pii=S0097316516300553&_rdoc=1&_issn=00973165&md5=530beefd46691b78d38695776ba81054">class="imgLazyJSB inlineImage" height="16" width="120" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0097316516300553-si4.gif">class="mathContainer hidden">class="mathCode">${\lim \inf }_{n\to \infty }{c}_x(n)$. We show that if x   is a Sturmian word, then class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300553&_mathId=si175.gif&_user=111111111&_pii=S0097316516300553&_rdoc=1&_issn=00973165&md5=613d722fe1223fa3944abe61611e4ddd">class="imgLazyJSB inlineImage" height="16" width="150" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0097316516300553-si175.gif">class="mathContainer hidden">class="mathCode">${\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  , class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300553&_mathId=si378.gif&_user=111111111&_pii=S0097316516300553&_rdoc=1&_issn=00973165&md5=5daaa8f5840c21cc564c28659f8f143e">class="imgLazyJSB inlineImage" height="16" width="169" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0097316516300553-si378.gif">class="mathContainer hidden">class="mathCode">${\lim \inf }_{n\to \infty }{c}_t(n)=+\infty$.