Extensions of rich words
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 D ? ( w ) = min { D ( z ) | 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.
rich words palindromes defect combinatorics on words sturmian words two-dimensional words