The theorem of Fine and Wilf for relational periods

Vesa Halava; Tero Harju; Tomi Kärki

RAIRO - Theoretical Informatics and Applications (2008)

  • 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 43.2 (2008): 209-220. <http://eudml.org/doc/92912>.

@article{Halava2008,
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},
keywords = {Period; partial word; compatibility; Fine; Wilf.; period; Wilf},
language = {eng},
month = {6},
number = {2},
pages = {209-220},
publisher = {EDP Sciences},
title = {The theorem of Fine and Wilf for relational periods},
url = {http://eudml.org/doc/92912},
volume = {43},
year = {2008},
}

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
DA - 2008/6//
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.; period; Wilf
UR - http://eudml.org/doc/92912
ER -

References

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

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.