We introduce and study a complex
ity 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">cx(n)class="mathContainer hidden">class="mathCode">, called
cyclic complexity, which counts the number of conjugacy
classes of factors of length
n of an infin
ite word
x. We extend the well-known Morse–Hedlund theorem to the setting of cyclic complex
ity by showing that a word is ultimately periodic if and only if
it has bounded cyclic complex
ity. Unlike most complex
ity functions, cyclic complex
ity 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 complex
ity 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">cx(n)=1class="mathContainer hidden">class="mathCode"> 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"> implies
x is periodic,
it is natural to consider the quant
ity
class="mathmlsrc">itle="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">. We show that if
x is a Sturmian word, then
class="mathmlsrc">itle="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">. We prove however that this is not a characterization of Sturmian words by exhib
iting a restricted
class of Toepl
itz words, including the period-doubling word, which also verify this same cond
ition on the lim
it infimum. In contrast we show that, for the Thue–Morse word
t ,
class="mathmlsrc">itle="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">.