A1 Refereed original research article in a scientific journal

Extensions of rich words




AuthorsJetro Vesti

PublisherELSEVIER SCIENCE BV

Publication year2014

Journal: Theoretical Computer Science

Journal name in sourceTHEORETICAL COMPUTER SCIENCE

Journal acronymTHEOR COMPUT SCI

Volume548

First page 14

Last page24

Number of pages11

ISSN0304-3975

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

Web address http://www.journals.elsevier.com/theoretical-computer-science/


Abstract

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 26/11/2024 07:40:44 PM