A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Extensions of rich words
Tekijät: Jetro Vesti
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2014
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 548
Aloitussivu: 14
Lopetussivu: 24
Sivujen määrä: 11
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2014.06.033
Verkko-osoite: http://www.journals.elsevier.com/theoretical-computer-science/
The defect of a finite word w is defined by D(w) = vertical bar w + 1 - vertical bar Pal(w)vertical bar. This concept has been studied in various papers. Here, we will define a new concept, infinite defect. For a finite word w the definition is D-infinity(w) = min{D(z) vertical bar z is an infinite word which has factor w}. We will show that the infinite defect of a finite word is always finite and give some upper bounds for it. The difference between defect and infinite defect is also investigated. We will also give an upper and a lower bound for the number of rich words. A new class of words, two-dimensional rich words, is also introduced. (C) 2014 Elsevier B.V. All rights reserved.