Extensions of rich words (Q401472): Difference between revisions

A \textit{palindrome} is a word equal to its mirror image. It is known that a finite word of length \(n\) contains at most \(n+1\) distinct palindromic factors. The \textit{(palindromic) defect} of a finite word is the difference between this maximum possible number and the actual number of palindromic factors. The \textit{defect of an infinite word} is the supremum (possibly equal to \(\infty\)) of the defects of its finite factors. The \textit{infinite defect} of a finite word is the minimum defect of an infinite word containing it as a factor. Words (finite or infinite) with zero defect are called rich. It has been shown earlier that every finite rich word can be extended by a suitable suffix (not containing new symbols) to a longer rich word. The present paper shows that every non-unary rich word has two, but not necessarily three, such extensions differing in the last symbol only. It proves that the infinite defect of a finite word is always finite and provides some facts about the relationship between the defect and the infinite defect of a finite word, as well as upper and lower bounds on the number of rich words. Finally, two-dimensional rich words are introduced. A two-dimensional word, as considered by the authors, is the infinite grid \(\mathbb{Z}^{2}\) where some positions are labeled by symbols of a finite alphabet. Such a word is rich if each of its contiguous (without gaps) row or column factors is rich. It is shown that a binary two-dimensional word where all symbol-labeled positions occur within a \(6\times6\) square, can be extended to a rich plane.