Voir la notice de l'article provenant de la source Numdam
Recently, Constantinescu and Ilie proved a variant of the well-known periodicity theorem of Fine and Wilf in the case of two relatively prime abelian periods and conjectured a result for the case of two non-relatively prime abelian periods. In this paper, we answer some open problems they suggested. We show that their conjecture is false but we give bounds, that depend on the two abelian periods, such that the conjecture is true for all words having length at least those bounds and show that some of them are optimal. We also extend their study to the context of partial words, giving optimal lengths and describing an algorithm for constructing optimal words.
@article{ITA_2013__47_3_215_0,
author = {Blanchet-Sadri, Francine and Simmons, Sean and Tebbe, Amelia and Veprauskas, Amy},
title = {Abelian periods, partial words, and an extension of a theorem of {Fine} and {Wilf}},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {215--234},
publisher = {EDP-Sciences},
volume = {47},
number = {3},
year = {2013},
doi = {10.1051/ita/2013034},
mrnumber = {3103125},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2013034/}
}
TY - JOUR AU - Blanchet-Sadri, Francine AU - Simmons, Sean AU - Tebbe, Amelia AU - Veprauskas, Amy TI - Abelian periods, partial words, and an extension of a theorem of Fine and Wilf JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2013 SP - 215 EP - 234 VL - 47 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2013034/ DO - 10.1051/ita/2013034 LA - en ID - ITA_2013__47_3_215_0 ER -
%0 Journal Article %A Blanchet-Sadri, Francine %A Simmons, Sean %A Tebbe, Amelia %A Veprauskas, Amy %T Abelian periods, partial words, and an extension of a theorem of Fine and Wilf %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2013 %P 215-234 %V 47 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2013034/ %R 10.1051/ita/2013034 %G en %F ITA_2013__47_3_215_0
Blanchet-Sadri, Francine; Simmons, Sean; Tebbe, Amelia; Veprauskas, Amy. Abelian periods, partial words, and an extension of a theorem of Fine and Wilf. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 3, pp. 215-234. doi: 10.1051/ita/2013034
Cité par Sources :