A1 Refereed original research article in a scientific journal
Overlap-freeness in infinite partial words
Authors: Halava V, Harju T, Karki T, Seebold P
Publisher: ELSEVIER SCIENCE BV
Publication year: 2009
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 410
Issue: 8-10
First page : 943
Last page: 948
Number of pages: 6
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2008.12.041
Abstract
We prove that there exist infinitely many infinite overlap-free binary partial words containing at least one hole. Moreover, we show that these words cannot contain more than one hole and the only hole must Occur either in the first or in the second position. We define that a partial word is k-overlap-free if it does not contain a factor of the form xyxyx where the length of x is at least k. We prove that there exist infinitely many 2-overlap-free binary partial words containing an infinite number of holes. (C) 2009 Elsevier B.V. All rights reserved.
We prove that there exist infinitely many infinite overlap-free binary partial words containing at least one hole. Moreover, we show that these words cannot contain more than one hole and the only hole must Occur either in the first or in the second position. We define that a partial word is k-overlap-free if it does not contain a factor of the form xyxyx where the length of x is at least k. We prove that there exist infinitely many 2-overlap-free binary partial words containing an infinite number of holes. (C) 2009 Elsevier B.V. All rights reserved.
UTU Research Portal