Issue |
RAIRO-Theor. Inf. Appl.
Volume 47, Number 3, July-August 2013
|
|
---|---|---|
Page(s) | 215 - 234 | |
Section | « Journées Montoises d’Informatique Théorique » 2010 | |
DOI | https://doi.org/10.1051/ita/2013034 | |
Published online | 25 April 2013 |
Abelian periods, partial words, and an extension of a theorem of Fine and Wilf∗
1 Department of Computer Science, University of North Carolina,
P.O. Box 26170, Greensboro, NC 27402–6170, USA.
blanchet@uncg.edu
2 Department of Mathematics,
Massachusetts Institute of Technology, Building 2, Room 236, 77 Massachusetts Avenue,
Cambridge, MA
02139–4307,
USA
3 Department of Mathematics, University
of Illinois, 1409 W. Green
Street, Urbana,
IL
61801,
USA
4 Department of Mathematics, The
University of Arizona, 617 N. Santa
Rita Ave., P.O. Box
210089
Tucson, AZ
85721–0089,
USA
Received:
2
November
2010
Accepted:
21
January
2013
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.
Mathematics Subject Classification: 68R15 / 68Q25
Key words: Combinatorics on words / Fine and Wilf’s theorem / partial words / abelian periods / periods / optimal lengths
This material is based upon work supported by the National Science Foundation under Grant Nos. DMS–0754154 and DMS–1060775. The Department of Defense is also gratefully acknowledged. Part of this paper was presented at JM 2010 [9].
This article was submitted within the framework of the “Journées Montoises 2010”.
© EDP Sciences 2013
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.