Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Relational Fine and Wilf Words

Relational Fine and Wilf Words

Vesa Halava, Tero Harju, Tomi Kärki, Luca Q. Zamboni, Relational Fine and Wilf Words. TUCS Technical Reports 839, Turku Centre for Computer Science, 2007.

Abstract:

We consider interaction properties of relational periods, where the relation is a compatibility relation on words induced by a relation
on letters. By the famous theorem of Fine and Wilf, $p+q-\gcd(p,q)-1$ is the maximal length of a word having periods $p$ and $q$ but not period $\gcd(p,q)$. Such words of maximal length are called extremal
Fine and Wilf words. In this paper we study properties of the corresponding words in a relational variation of the Fine and Wilf theorem.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaHaKaZa07a,
  title = {Relational Fine and Wilf Words},
  author = {Halava, Vesa and Harju, Tero and Kärki, Tomi and Zamboni, Luca Q.},
  number = {839},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2007},
  keywords = {period, compatibility relation, partial word, Fine, Wilf},
  ISBN = {978-952-12-1948-1},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication