Critical factorisation in square-free words



: Harju Tero

Publisher: EDP Sciences

: 2022

: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications

: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS

: RAIRO-THEOR INF APPL

:  3

: 56

: 8

: 0988-3754

: 1290-385X

DOI: https://doi.org/10.1051/ita/2022003

: https://www.rairo-ita.org/articles/ita/abs/2022/01/ita210035/ita210035.html

: https://research.utu.fi/converis/portal/detail/Publication/174787467


A position p in a word w is critical if the minimal local period at p is equal to the global period of w. According to the Critical Factorisation Theorem all words of length at least two have a critical point. We study the number eta(w) of critical points of square-free ternary words w, i.e., words over a three letter alphabet. We show that the sufficiently long square-free words w satisfy eta(w) <=|w|- 5 where |w| denotes the length of w. Moreover, the bound |w|- 5 is reached by infinitely many words. On the other hand, every square-free word w has at least |w|/4 critical points, and there is a sequence of these words closing to this bound.

Last updated on 2024-26-11 at 15:44