The theorem of Fine and Wilf for relational periods

Vesa Halava; Tero Harju; Tomi Kärki

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2009)

  • Volume: 43, Issue: 2, page 209-220
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Halava, Vesa, Harju, Tero, and Kärki, Tomi. "The theorem of Fine and Wilf for relational periods." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 43.2 (2009): 209-220. <http://eudml.org/doc/245895>.

@article{Halava2009,
abstract = {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.},
author = {Halava, Vesa, Harju, Tero, Kärki, Tomi},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {period; partial word; compatibility; Fine; Wilf},
language = {eng},
number = {2},
pages = {209-220},
publisher = {EDP-Sciences},
title = {The theorem of Fine and Wilf for relational periods},
url = {http://eudml.org/doc/245895},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Halava, Vesa
AU - Harju, Tero
AU - Kärki, Tomi
TI - The theorem of Fine and Wilf for relational periods
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2009
PB - EDP-Sciences
VL - 43
IS - 2
SP - 209
EP - 220
AB - 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.
LA - eng
KW - period; partial word; compatibility; Fine; Wilf
UR - http://eudml.org/doc/245895
ER -

References

top
  1. [1] J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135–141. Zbl0916.68120MR1687780
  2. [2] F. Blanchet-Sadri, A periodicity result of partial words with one hole. Comput. Math. Appl. 46 (2003) 813–820. Zbl1074.68046MR2020440
  3. [3] F. Blanchet-Sadri, Periodicity on partial words. Comput. Math. Appl. 47 (2004) 71–82. Zbl1068.68110MR2062726
  4. [4] F. Blanchet-Sadri, Codes, orderings, and partial words. Theoret. Comput. Sci. 329 (2004) 177–202. Zbl1086.68108MR2103647
  5. [5] F. Blanchet-Sadri and A. Chriscoe, Local periods and binary partial words: an algorithm. Theoret. Comput. Sci. 314 (2004) 189–216. Zbl1070.68061MR2033749
  6. [6] F. Blanchet-Sadri and S. Duncan, Partial words and the critical factorization theorem. J. Combin. Theory Ser. A 109 (2005) 221–245. Zbl1073.68067MR2121025
  7. [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. Zbl0988.68142MR1871078
  8. [8] N.J. Fine and H.S. Wilf, Uniqueness theorem for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109–114. Zbl0131.30203MR174934
  9. [9] V. Halava, T. Harju and T. Kärki, Relational codes of words. Theoret. Comput. Sci. 389 (2007) 237–249. Zbl1143.68036MR2363375
  10. [10] V. Halava, T. Harju and T. Kärki, Defect theorems with compatibility relation. Semigroup Forum 76 (2008) 1–24. Zbl1146.20036MR2367152
  11. [11] P. Leupold, Partial words for DNA coding. Lect. Notes Comput. Sci. 3384 (2005) 224–234. Zbl1116.68462MR2179040
  12. [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. Zbl1151.68568MR2081340
  13. [13] A.M. Shur and Yu.V. Gamzova, Partial words and the interaction property of periods. Izv. Math. 68 (2004) 405–428. Zbl1088.68147MR2058005

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.