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

Square-Free Partial Words

Vesa Halava, Tero Harju, Tomi Kärki, Square-Free Partial Words. TUCS Technical Reports 893, Turku Centre for Computer Science, 2008.

Abstract:

We say that a partial word $w$ over an alphabet $A$ is square-free if every factor $xx'$ of $w$ such that $x$ and $x'$ are compatible is either of the form $ha$ or $ah$ where $h$ is a hole and $a$ is a letter in $A$. We prove that there exist uncountably many square-free partial words over a ternary alphabet with an infinite number of holes.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaHaKa08b,
  title = {Square-Free Partial Words},
  author = {Halava, Vesa and Harju, Tero and Kärki, Tomi},
  number = {893},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2008},
  keywords = {Repetitions, square-freeness, partial words, Thue-Morse word, Leech word, infinite words},
  ISBN = {978-952-12-2097-5},
}

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

Edit publication