Avoiding conjugacy classes on the 5-letter alphabet
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 54 (2020), article no. 2

We construct an infinite word w over the 5-letter alphabet such that for every factor f of w of length at least two, there exists a cyclic permutation of f that is not a factor of w. In other words, w does not contain a non-trivial conjugacy class. This proves the conjecture in Gamard et al. [Theoret. Comput. Sci. 726 (2018) 1–4].

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ita/2020003
Classification : 68R15
Keywords: Combinatorics on words, conjugacy classes 
@article{ITA_2020__54_1_A2_0,
     author = {Badkobeh, Golnaz and Ochem, Pascal},
     title = {Avoiding conjugacy classes on the 5-letter alphabet},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     year = {2020},
     publisher = {EDP Sciences},
     volume = {54},
     doi = {10.1051/ita/2020003},
     mrnumber = {4078186},
     zbl = {1457.68226},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2020003/}
}
TY  - JOUR
AU  - Badkobeh, Golnaz
AU  - Ochem, Pascal
TI  - Avoiding conjugacy classes on the 5-letter alphabet
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2020
VL  - 54
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2020003/
DO  - 10.1051/ita/2020003
LA  - en
ID  - ITA_2020__54_1_A2_0
ER  - 
%0 Journal Article
%A Badkobeh, Golnaz
%A Ochem, Pascal
%T Avoiding conjugacy classes on the 5-letter alphabet
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2020
%V 54
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ita/2020003/
%R 10.1051/ita/2020003
%G en
%F ITA_2020__54_1_A2_0
Badkobeh, Golnaz; Ochem, Pascal. Avoiding conjugacy classes on the 5-letter alphabet. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 54 (2020), article no. 2. doi: 10.1051/ita/2020003

[1] K. A. Baker, G.F. Mcnulty and W. Taylor, Growth problems for avoidable words. Theoret. Comput. Sci. 69 (1989) 19–345. | MR | Zbl | DOI

[2] D. R. Bean, A. Ehrenfeucht and G.F. Mcnulty, Avoidable patterns in strings of symbols. Pacific J. Math. 85 (1979) 261–294. | MR | Zbl | DOI

[3] J. P. Bell and B. W. Madill, Iterative Algebras. Algebr. Represent. Theor. 18 (2015) 1533–1546. | MR | Zbl | DOI

[4] R. J. Clark, Avoidable formulas in combinatorics on words. Ph.D. thesis, University of California, Los Angeles. Available at http://www.lirmm.fr/~ochem/morphisms/clark˙thesis.pdf (2001). | MR

[5] G. Gamard, P. Ochem, G. Richomme and P. Séébold, Avoidability of circular formulas. Theoret. Comput. Sci. 726 (2018) 1–4. | MR | Zbl | DOI

[6] L. Ilie, P. Ochem and J. O. Shallit, A generalization of repetition threshold. Theoret. Comput. Sci. 92 (2004) 71–76. | MR

[7] P. Ochem, A generator of morphisms for infinite words. RAIRO: ITA 40 (2006) 427–441. | MR | Zbl | Numdam

[8] A. I. Zimin, Blocking sets of terms. Math. USSR Sbornik 47 (1984) 353–364. | MR | Zbl | DOI

Cité par Sources :