Name
Abstract | ||
|---|---|---|
We introduce and study a complexity function on words c x ( 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 c x ( n ) = 1 for some n ź 1 implies x is periodic, it is natural to consider the quantity lim inf n ź ∞ c x ( n ) . We show that if x is a Sturmian word, then lim inf n ź ∞ c x ( 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, lim inf n ź ∞ c t ( n ) = + ∞ . |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-662-44522-8_14 | mathematical foundations of computer science |
Keywords | DocType | Volume |
Cyclic complexity,Factor complexity,Sturmian words | Journal | 145 |
Issue | ISSN | Citations |
C | 0097-3165 | 0 |
PageRank | References | Authors |
0.34 | 8 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Julien Cassaigne | 1 | 282 | 40.80 |
| Gabriele Fici | 2 | 252 | 30.13 |
| Marinella Sciortino | 3 | 225 | 22.34 |
| Luca Q. Zamboni | 4 | 253 | 27.58 |