We introduce and study a
complexity function on words
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), 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
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)=1 for some
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≥1 implies
x is periodic, it is natural to consider the quantity
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">data-inlimgeid="1-s2.0-S0097316516300553-si4.gif">. We show that if
x is a Sturmian word, then
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">data-inlimgeid="1-s2.0-S0097316516300553-si175.gif">. 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 ,
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">data-inlimgeid="1-s2.0-S0097316516300553-si378.gif">.