The theorem of Fine and Wilf for relational periods
Halava, Vesa ; Harju, Tero ; Kärki, Tomi
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009), p. 209-220 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We consider relational periods, where the relation is a compatibility relation on words induced by a relation on letters. We prove a variant of the theorem of Fine and Wilf for a (pure) period and a relational period.

Publié le : 2009-01-01
DOI : https://doi.org/10.1051/ita:2008025
Classification:  68R15 
@article{ITA_2009__43_2_209_0,
     author = {Halava, Vesa and Harju, Tero and K\"arki, Tomi},
     title = {The theorem of Fine and Wilf for relational periods},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {43},
     year = {2009},
     pages = {209-220},
     doi = {10.1051/ita:2008025},
     mrnumber = {2512255},
     zbl = {1166.68035},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2009__43_2_209_0}
}

Halava, Vesa; Harju, Tero; Kärki, Tomi. The theorem of Fine and Wilf for relational periods. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) pp. 209-220. doi : 10.1051/ita:2008025. http://gdmltest.u-ga.fr/item/ITA_2009__43_2_209_0/

[1] J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135-141. | MR 1687780 | Zbl 0916.68120

[2] F. Blanchet-Sadri, A periodicity result of partial words with one hole. Comput. Math. Appl. 46 (2003) 813-820. | MR 2020440 | Zbl 1074.68046

[3] F. Blanchet-Sadri, Periodicity on partial words. Comput. Math. Appl. 47 (2004) 71-82. | MR 2062726 | Zbl 1068.68110

[4] F. Blanchet-Sadri, Codes, orderings, and partial words. Theoret. Comput. Sci. 329 (2004) 177-202. | MR 2103647 | Zbl 1086.68108

[5] F. Blanchet-Sadri and A. Chriscoe, Local periods and binary partial words: an algorithm. Theoret. Comput. Sci. 314 (2004) 189-216. | MR 2033749 | Zbl 1070.68061

[6] F. Blanchet-Sadri and S. Duncan, Partial words and the critical factorization theorem. J. Combin. Theory Ser. A 109 (2005) 221-245. | MR 2121025 | Zbl 1073.68067

[7] F. Blanchet-Sadri and R.A. Hegstrom, Partial words and a theorem of Fine and Wilf revisited. Theoret. Comput. Sci. 270 (2002) 401-419. | MR 1871078 | Zbl 0988.68142

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

[9] V. Halava, T. Harju and T. Kärki, Relational codes of words. Theoret. Comput. Sci. 389 (2007) 237-249. | MR 2363375 | Zbl 1143.68036

[10] V. Halava, T. Harju and T. Kärki, Defect theorems with compatibility relation. Semigroup Forum 76 (2008) 1-24. | MR 2367152 | Zbl 1146.20036

[11] P. Leupold, Partial words for DNA coding. Lect. Notes Comput. Sci. 3384 (2005) 224-234. | MR 2179040 | Zbl 1116.68462

[12] A.M. Shur and Y.V. Gamzova, Periods' interaction property for partial words, in Proceedings of Words'03, edited by T. Harju and J. Karhumäki. TUCS General Publication 27 (2003) 75-82. | MR 2081340 | Zbl 1151.68568

[13] A.M. Shur and Yu.V. Gamzova, Partial words and the interaction property of periods. Izv. Math. 68 (2004) 405-428. | MR 2058005 | Zbl 1088.68147