Name
Abstract | ||
|---|---|---|
Motivated by the extension of the critical factorization theorem to infinite words, we study the (local) periodicity function, i.e. the function that, for any position in a word, gives the size of the shortest square centered in that position. We prove that this function characterizes any binary word up to exchange of letters. We then introduce a new complexity function for words (the periodicity complexity) that, for any position in the word, gives the average value of the periodicity function up to that position. The new complexity function is independent from the other commonly used complexity measures as, for instance, the factor complexity. Indeed, whereas any infinite word with bounded factor complexity is periodic, we will show a recurrent non-periodic word with bounded periodicity complexity. Further, we will prove that the periodicity complexity function grows as Theta(log n) in the case of the Fibonacci infinite word and that it grows as Theta(n) in the case of the Thue-Morse word. Finally, we will show examples of infinite recurrent words with arbitrary high periodicity complexity. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1142/S0218196713400080 | INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION |
Keywords | Field | DocType |
Combinatorics on words, complexity functions, periodicity, critical factorization theorem | Discrete mathematics,Binary logarithm,Average-case complexity,Combinatorics,Complexity function,Complexity index,Combinatorics on words,Mathematics,Bounded function,Fibonacci number,Weierstrass factorization theorem | Journal |
Volume | Issue | ISSN |
23 | 4 | 0218-1967 |
Citations | PageRank | References |
3 | 0.47 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Filippo Mignosi | 1 | 569 | 99.71 |
| Antonio Restivo | 2 | 697 | 107.05 |