Cyclic complexity of words (Q507796)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Cyclic complexity of words |
scientific article; zbMATH DE number 6682584
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Cyclic complexity of words |
scientific article; zbMATH DE number 6682584 |
Statements
Cyclic complexity of words (English)
0 references
9 February 2017
0 references
A new complexity function on words, called cyclic complexity, is introduced and studied. This function counts the number of conjugacy classes of factors of length \(n\) of an infinite word \(x\). Cyclic complexity distinguishes between Sturmian words of different slopes, yet can not provide a strict characterization of Sturmian words. A very useful extension of the Morse-Hedlund theorem is also presented and used in this paper.
0 references
cyclic complexity
0 references
factor complexity
0 references
Sturmian words
0 references
Toeplitz words
0 references
Morse-Hedlund theorem
0 references
