A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Rich square-free words
Tekijät: Vesti J
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2017
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 687
Aloitussivu: 48
Lopetussivu: 61
Sivujen määrä: 14
ISSN: 0304-3975
eISSN: 1879-2294
DOI: https://doi.org/10.1016/j.tcs.2017.05.003
Tiivistelmä
A word w is rich if it has vertical bar w vertical bar + 1 distinct palindromic factors, including the empty word. A word is square-free if it does not have a factor uu, where u is a non-empty word.Pelantova and Starosta (2013) [16] proved that every infinite rich word contains a square. We will give another proof for that result. Pelantova and Starosta marked with r(n) the length of a longest rich square-free word on an alphabet of size n. The exact value of r(n) was left as an open question. We will give an upper and a lower bound for r(n). The lower bound is conjectured to be exact but it is not explicit.We will also generalize the notion of repetition threshold for a limited class of infinite words. The repetition thresholds for episturmian and rich words are left as an open question. (C) 2017 Elsevier B.V. All rights reserved.
A word w is rich if it has vertical bar w vertical bar + 1 distinct palindromic factors, including the empty word. A word is square-free if it does not have a factor uu, where u is a non-empty word.Pelantova and Starosta (2013) [16] proved that every infinite rich word contains a square. We will give another proof for that result. Pelantova and Starosta marked with r(n) the length of a longest rich square-free word on an alphabet of size n. The exact value of r(n) was left as an open question. We will give an upper and a lower bound for r(n). The lower bound is conjectured to be exact but it is not explicit.We will also generalize the notion of repetition threshold for a limited class of infinite words. The repetition thresholds for episturmian and rich words are left as an open question. (C) 2017 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali