A1 Refereed original research article in a scientific journal
Extensions of rich words
Authors: Jetro Vesti
Publisher: ELSEVIER SCIENCE BV
Publication year: 2014
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 548
First page : 14
Last page: 24
Number of pages: 11
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2014.06.033
Web address : 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.