A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Critical factorisation in square-free words
Tekijät: Harju Tero
Kustantaja: EDP Sciences
Julkaisuvuosi: 2022
Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Tietokannassa oleva lehden nimi: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Lehden akronyymi: RAIRO-THEOR INF APPL
Artikkelin numero: 3
Vuosikerta: 56
Sivujen määrä: 8
ISSN: 0988-3754
eISSN: 1290-385X
DOI: https://doi.org/10.1051/ita/2022003
Verkko-osoite: https://www.rairo-ita.org/articles/ita/abs/2022/01/ita210035/ita210035.html
Rinnakkaistallenteen osoite: 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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
