Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Extensions of Rich Words

Extensions of Rich Words

Jetro Vesti, Extensions of Rich Words. Theoretical Computer Science 548, 14–24, 2014.

http://dx.doi.org/10.1016/j.tcs.2014.06.033

Abstract:

A word w is rich if it has |w|+1|w|+1 many distinct palindromic factors, including the empty word. This article contains several results about rich words, particularly related to extending them. A word w can be eventually extended richly in n ways if there exists a finite word u and n distinct letters a∈Alph(w)a∈Alph(w) such that wua is rich. We will prove that every (non-unary) rich word can be eventually extended richly in at least two different ways, but not always in three or more ways. We will also prove that every rich word can be extended to both periodic and aperiodic infinite rich words.

The defect of a finite word w is defined by D(w)=|w|+1−|Pal(w)|D(w)=|w|+1−|Pal(w)|. 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 View the MathML sourceD∞(w)=min{D(z)|zis an infinite word which has factorw}. 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.

BibTeX entry:

@ARTICLE{jVesti_Jetro14a,
  title = {Extensions of Rich Words},
  author = {Vesti, Jetro},
  journal = {Theoretical Computer Science},
  volume = {548},
  publisher = {Elsevier},
  pages = {14–24},
  year = {2014},
  keywords = {Combinatorics on words; Palindromes; Rich words; Sturmian words; Defect; Two-dimensional words},
  ISSN = {0304-3975},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication