A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Extensions of rich words




TekijätJetro Vesti

KustantajaELSEVIER SCIENCE BV

Julkaisuvuosi2014

Lehti: Theoretical Computer Science

Tietokannassa oleva lehden nimiTHEORETICAL COMPUTER SCIENCE

Lehden akronyymiTHEOR COMPUT SCI

Vuosikerta548

Aloitussivu14

Lopetussivu24

Sivujen määrä11

ISSN0304-3975

DOIhttps://doi.org/10.1016/j.tcs.2014.06.033

Verkko-osoitehttp://www.journals.elsevier.com/theoretical-computer-science/


Tiivistelmä

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.




Last updated on