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

Overlap-Freeness in Infinite Partial Words

Vesa Halava, Tero Harju, Tomi Kärki, Overlap-Freeness in Infinite Partial Words. TUCS Technical Reports 888, Turku Centre for Computer Science, 2008.

Abstract:

We prove that there exist infinitely many infinite overlap-free
binary partial words with one hole. Moreover, we show that there
exist infinitely many binary partial words with an infinite number
of holes which are 3-overlap-free, i.e., they are cube-free and they
do not contain a factor of the form xyxyx where the length of x
is at least three and y is nonempty.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaHaKa08a,
  title = {Overlap-Freeness in Infinite Partial Words},
  author = {Halava, Vesa and Harju, Tero and Kärki, Tomi},
  number = {888},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2008},
  keywords = {Repetition-freeness, k-free, overlap, partial words, Thue-Morse word, infinite words},
  ISBN = {978-952-12-2075-3},
}

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

Edit publication