---

---

Vesa Halava, Tero Harju, Tomi Kärki:
Overlap-Freeness in Infinite Partial Words

ISBN: 978-952-12-2075-3

Techreport
Year: 2008
Month: Feb
Number: 888
Institution: TUCS
Keywords: Repetition-freeness, k-free, overlap, partial words, Thue-Morse word, infinite words
Laboratory: Discrete Mathematics for Information Technology

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.

Download full text