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

defectrich wordspalindromesSturmian wordstwo-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.

Recommendations

• A unique extension of rich words
• On words with the zero palindromic defect
• On the number of rich words
• Rich words containing two given factors
• Palindromic richness

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• A connection between palindromic and factor complexity using return words
• A new characteristic property of rich words
• A remark on morphic sturmian words
• Burrows-Wheeler transform and palindromic richness
• Complexity and palindromic defect of infinite words
• Episturmian words and some constructions of de Luca and Rauzy
• Infinite words with finite defect
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• On a conjecture on bidimensional words.
• On periodicity of two-dimensional words
• Palindromic complexity of infinite words associated with simple Parry numbers
• Palindromic richness
• Periodicity and local complexity
• Proof of the Brlek-Reutenauer conjecture
• Rich, Sturmian, and trapezoidal words
• Tilings and rotations on the torus: A two-dimensional generalization of Sturmian sequences

Cited in

(11)

• ALMOST RICH WORDS AS MORPHIC IMAGES OF RICH WORDS
• Palindromic factorization of rich words
• On Morphisms Preserving Palindromic Richness
• A unique extension of rich words
• Ostrowski-automatic sequences: theory and applications
• Rich and Periodic-Like Words
• Rich square-free words
• Upper bound for palindromic and factor complexity of rich words
• Rich words in the block reversal of a word
• On generalized highly potential words
• The repetition threshold for binary rich words

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)