On multiperiodic words
Holub, Štěpán
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006), p. 583-591 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2006-01-01
DOI : https://doi.org/10.1051/ita:2006042
Classification:  68R15 
@article{ITA_2006__40_4_583_0,
     author = {Holub, \v St\v ep\'an},
     title = {On multiperiodic words},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {40},
     year = {2006},
     pages = {583-591},
     doi = {10.1051/ita:2006042},
     mrnumber = {2277051},
     zbl = {1110.68121},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2006__40_4_583_0}
}

Holub, Štěpán. On multiperiodic words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) pp. 583-591. doi : 10.1051/ita:2006042. http://gdmltest.u-ga.fr/item/ITA_2006__40_4_583_0/

[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