• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On the Number of Frames in Binary Words

Tero Harju, Tomi Kärki, On the Number of Frames in Binary Words. Theoretical Computer Science 412, 5276–5284, 2011.

http://dx.doi.org/10.1016/j.tc

Abstract:

A frame is a square uu, where u is an unbordered word.
Let F(n) denote the maximum number of distinct frames in
a binary word of length n. We count this number for small
values of n and show that F(n) is at most n/2+8 for all n
and greater than 7n/30−e for any positive e and infinitely many n.
We also show that Fibonacci words, which are known to contain
plenty of distinct squares, have only a few frames.
Moreover, by modifying the Thue–Morse word,
we prove that the minimum number of occurrences of frames in
a word of length n is n/2−2.

BibTeX entry:

@ARTICLE{jHaK,
  title = {On the Number of Frames in Binary Words},
  author = {Harju, Tero and Kärki, Tomi},
  journal = {Theoretical Computer Science},
  volume = {412},
  pages = {5276–5284},
  year = {2011},
  keywords = {frames, unbordered words, squares, combinatorics on words},
}

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

Publication Forum rating of this publication: level 2

Edit publication