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

On the Number of Squares in Partial Words

Vesa Halava, Tero Harju, Tomi Kärki, On the Number of Squares in Partial Words. TUCS Technical Reports 896, Turku Centre for Computer Science, 2009.

Abstract:

The theorem of Fraenkel and Simpson states that the maximum number
of distinct squares that a word $w$ of length $n$ can contain is
less than $2n$. This is based on the fact that no more than two
squares can have their last occurrences starting at the same
position. In this paper we show that the maximum number of the last
occurrences of squares per position in a partial word containing one
hole is $2k$, where $k$ is the size of the alphabet. Moreover, we
prove that the number of distinct squares in a partial word with one
hole and of length $n$ is less than $4n$, regardless of the size of
the alphabet. For binary partial words, this upper bound can be
reduced to $3n$.

Files:

Abstract in PDF-format

BibTeX entry:

@TECHREPORT{tHaHaKa08c,
  title = {On the Number of Squares in Partial Words},
  author = {Halava, Vesa and Harju, Tero and Kärki, Tomi},
  number = {896},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2009},
  keywords = {Squares, partial words, theorem of Fraenkel and Simpson},
  ISBN = {978-952-12-2102-6},
}

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

Edit publication