Extensions of rich words

DOI10.1016/J.TCS.2014.06.033MaRDI QIDQ401472zbMATH OpenOpenAlexFDO

Authors Jetro Vesti

Publication date 27 August 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.4350

zbMATH Keywords

defect palindromes rich words Sturmian words two-dimensional words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: In [X. Droubay et al, Episturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci. 255 (2001)], it was proved that every word w has at most |w|+1 many distinct palindromic factors, including the empty word. The unified study of words which achieve this limit was initiated in [A. Glen et al, Palindromic richness, Eur. Jour. of Comb. 30 (2009)]. They called these words rich (in palindromes). This article contains several results about rich words and especially extending them. We say that a rich word w can be extended richly with a word u if wu is rich. Some notions are also made about the infinite defect of a word, the number of rich words of length n and two-dimensional rich words.

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.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Extensions of rich words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q401472)