A1 Refereed original research article in a scientific journal

Extensions of rich words




AuthorsJetro Vesti

PublisherELSEVIER SCIENCE BV

Publication year2014

JournalTheoretical 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 2024-26-11 at 19:40