Extensions of rich words (Q401472): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Anton Černý / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68R15 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6334624 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
palindromes | |||
Property / zbMATH Keywords: palindromes / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
rich words | |||
Property / zbMATH Keywords: rich words / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Sturmian words | |||
Property / zbMATH Keywords: Sturmian words / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
defect | |||
Property / zbMATH Keywords: defect / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
two-dimensional words | |||
Property / zbMATH Keywords: two-dimensional words / rank | |||
Normal rank |
Revision as of 17:28, 29 June 2023
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