A1 Refereed original research article in a scientific journal
Critical factorisation in square-free words
Authors: Harju Tero
Publisher: EDP Sciences
Publication year: 2022
Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Journal name in source: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Journal acronym: RAIRO-THEOR INF APPL
Article number: 3
Volume: 56
Number of pages: 8
ISSN: 0988-3754
eISSN: 1290-385X
DOI: https://doi.org/10.1051/ita/2022003
Web address : https://www.rairo-ita.org/articles/ita/abs/2022/01/ita210035/ita210035.html
Self-archived copy’s web address: 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.
Downloadable publication This is an electronic reprint of the original article. |  |
