A New Complexity Function for Words Based on Periodicity

Antonio Restivo, Filippo Mignosi

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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 Θ(log n) in the case of the Fibonacci infinite word and that it grows as Θ(n) in the case of the Thue–Morse word. Finally, we will show examples of infinite recurrent words with arbitrary high periodicity complexity.
Original languageEnglish
Pages (from-to)963-987
Number of pages25
JournalInternational Journal of Algebra and Computation
Volume23
Publication statusPublished - 2013

All Science Journal Classification (ASJC) codes

  • General Mathematics

Fingerprint

Dive into the research topics of 'A New Complexity Function for Words Based on Periodicity'. Together they form a unique fingerprint.

Cite this