We introduce and study a complexity function on
words 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
cx(n)=1 for some
n≥1 implies
x is periodic, it is natural to consider the quantity
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">. We show that if
x is a Sturmian word, then
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">. 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 ,
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">.