Extensions of rich words (Q401472): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 1312.4350 / rank | |||
Normal rank |
Revision as of 14:22, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Extensions of rich words |
scientific article |
Statements
Extensions of rich words (English)
0 references
27 August 2014
0 references
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.
0 references
palindromes
0 references
rich words
0 references
Sturmian words
0 references
defect
0 references
two-dimensional words
0 references