Cyclic complexity of words

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 pe...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series A 2017-01, Vol.145, p.36-56
Main Authors: Cassaigne, Julien, Fici, Gabriele, Sciortino, Marinella, Zamboni, Luca Q.
Format: Article
Language:English
Subjects:
Cyclic complexity
Factor complexity
Sturmian words
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 liminfn→∞cx(n). We show that if x is a Sturmian word, then liminfn→∞cx(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, liminfn→∞ct(n)=+∞.
ISSN:0097-3165
1096-0899
DOI:10.1016/j.jcta.2016.07.002