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">cx(n)class="mathContainer hidden">class="mathCode">, 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">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 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">. 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">. 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">.