Square-free partial words
: Halava Vesa, Harju Tero, Kärki Tomi
Publisher: ELSEVIER SCIENCE BV
: 2008
: Information Processing Letters
: INFORMATION PROCESSING LETTERS
: INFORM PROCESS LETT
: 108
: 5
: 290
: 292
: 3
: 0020-0190
: 1872-6119
DOI: https://doi.org/10.1016/j.ipl.2008.06.001
: https://doi.org/10.1016/j.ipl.2008.06.001
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 lozenge a or a lozenge where lozenge is a hole and a is an element of A. We prove that there exist uncountably many square-free partial words over a ternary alphabet with an infinite number of holes.