On multiperiodic words
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 583-591.

In this note we consider the longest word, which has periods p 1 ,,p n , and does not have the period gcd(p 1 ,,p n ). The length of such a word can be established by a simple algorithm. We give a short and natural way to prove that the algorithm is correct. We also give a new proof that the maximal word is a palindrome.

DOI : https://doi.org/10.1051/ita:2006042
Classification : 68R15
Mots clés : periodicity, combinatorics on words
@article{ITA_2006__40_4_583_0,
     author = {Holub, \v{S}t\v{e}p\'an},
     title = {On multiperiodic words},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {583--591},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {4},
     year = {2006},
     doi = {10.1051/ita:2006042},
     zbl = {1110.68121},
     mrnumber = {2277051},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2006042/}
}
TY  - JOUR
AU  - Holub, Štěpán
TI  - On multiperiodic words
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
DA  - 2006///
SP  - 583
EP  - 591
VL  - 40
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2006042/
UR  - https://zbmath.org/?q=an%3A1110.68121
UR  - https://www.ams.org/mathscinet-getitem?mr=2277051
UR  - https://doi.org/10.1051/ita:2006042
DO  - 10.1051/ita:2006042
LA  - en
ID  - ITA_2006__40_4_583_0
ER  - 
Holub, Štěpán. On multiperiodic words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 583-591. doi : 10.1051/ita:2006042. http://www.numdam.org/articles/10.1051/ita:2006042/

[1] M.G. Castelli, F. Mignosi and A. Restivo, Fine and Wilf's theorem for three periods and a generalization of sturmian words. Theoret. Comput. Sci. 218 (1999) 83-94. | Zbl 0916.68114

[2] S. Constantinescu and L. Ilie, Generalised Fine and Wilf's theorem for arbitrary number of periods. Theoret. Comput. Sci. 339 (2005) 49-60. | Zbl 1127.68074

[3] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. | Zbl 0131.30203

[4] Š. Holub, A solution of the equation (x 1 2 x n 2 ) 3 =(x 1 3 x n 3 ) 2 , in Contributions to general algebra, 11 (Olomouc/Velké Karlovice, 1998), Heyn, Klagenfurt (1999) 105-111. | Zbl 0941.20066

[5] J. Justin, On a paper by Castelli, Mignosi, Restivo. Theoret. Inform. Appl. 34 (2000) 373-377. | Numdam | Zbl 0987.68056

[6] A. Lentin, Équations dans les monoïdes libres. Mathématiques et Sciences de l'Homme, No. 16, Mouton, (1972). | Zbl 0258.20058

[7] R. Tijdeman and L. Zamboni, Fine and Wilf words for any periods. Indag. Math. (N.S.) 14 (2003) 135-147. | Zbl 1091.68088

Cité par Sources :