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 : 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},
     mrnumber = {2277051},
     zbl = {1110.68121},
     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
SP  - 583
EP  - 591
VL  - 40
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2006042/
DO  - 10.1051/ita:2006042
LA  - en
ID  - ITA_2006__40_4_583_0
ER  - 
%0 Journal Article
%A Holub, Štěpán
%T On multiperiodic words
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 583-591
%V 40
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2006042/
%R 10.1051/ita:2006042
%G en
%F 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) 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

[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

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

[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

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

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

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

Cité par Sources :