Critical Factorisation in Square-Free Words
RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 3

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 η(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 η(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.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ita/2022003
Classification : 68R15
Keywords: Critical point, critical factorisation theorem, ternary words, square-free words 
@article{ITA_2022__56_1_A3_0,
     author = {Harju, Tero},
     title = {Critical {Factorisation} in {Square-Free} {Words}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     doi = {10.1051/ita/2022003},
     mrnumber = {4379607},
     zbl = {1493.68282},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2022003/}
}
TY  - JOUR
AU  - Harju, Tero
TI  - Critical Factorisation in Square-Free Words
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2022
VL  - 56
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2022003/
DO  - 10.1051/ita/2022003
LA  - en
ID  - ITA_2022__56_1_A3_0
ER  - 
%0 Journal Article
%A Harju, Tero
%T Critical Factorisation in Square-Free Words
%J RAIRO. Theoretical Informatics and Applications
%D 2022
%V 56
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2022003/
%R 10.1051/ita/2022003
%G en
%F ITA_2022__56_1_A3_0
Harju, Tero. Critical Factorisation in Square-Free Words. RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 3. doi: 10.1051/ita/2022003

[1] F. Blanchet-Sadri, J. D. Currie, N. Rampersad and N. Fox, Abelian complexity of fixed point of morphism 0↦ 012, 1↦ 02, 2↦1. Integers 14 (2014) a11. | MR | Zbl

[2] Y. Césari and M. Vincent, Une caractérisation des mots périodiques. C. R. Acad. Sci. Paris 286(A) (1978) 1175–1177. | MR | Zbl

[3] M. Crochemore and D. Perrin, Two-way string-matching. J. Assoc. Comput. Mach. 38 (1991) 651–675. | MR | Zbl | DOI

[4] J.-P. Duval, Périodes et répétitions des mots du monoïde libre. Theoret. Comput. Sci. 9 (1979) 17–26. | MR | Zbl | DOI

[5] T. Harju and D. Nowotka, Density of critical factorizations. Theor. Inform. Appl. 36 (2002) 315–327. | MR | Zbl | Numdam | DOI

[6] M. Lothaire, Combinatorics on words. Vol. 17 of Encyclopedia of Mathematics. Addison-Wesley, Reading, Massachusetts (1983). | MR | Zbl

[7] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, United Kingdom (2002). | Zbl | MR | DOI

[8] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Selsk. Skr., I Mat.-nat. Kl. Christiania 1 (1912) 1–67. | JFM

Cité par Sources :