Extensions of rich words (Q401472): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
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 | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2054815869 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1312.4350 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Palindromic complexity of infinite words associated with simple Parry numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Infinite words with finite defect / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Proof of the Brlek-Reutenauer conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A remark on morphic sturmian words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tilings and rotations on the torus: A two-dimensional generalization of Sturmian sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity and palindromic defect of infinite words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A connection between palindromic and factor complexity using return words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new characteristic property of rich words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rich, Sturmian, and trapezoidal words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Episturmian words and some constructions of de Luca and Rauzy / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a conjecture on bidimensional words. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Palindromic richness / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3659988 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4529547 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On periodicity of two-dimensional words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Periodicity and local complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Burrows-Wheeler transform and palindromic richness / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 23:18, 8 July 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
0 references