A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Overlap-freeness in infinite partial words
Tekijät: Halava V, Harju T, Karki T, Seebold P
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2009
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 410
Numero: 8-10
Aloitussivu: 943
Lopetussivu: 948
Sivujen määrä: 6
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2008.12.041
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali