Palindromic richness
From MaRDI portal
Publication:1003605
DOI10.1016/J.EJC.2008.04.006zbMATH Open1169.68040DBLPjournals/ejc/GlenJWZ09arXiv0801.1656OpenAlexW2913518517WikidataQ97016349 ScholiaQ97016349MaRDI QIDQ1003605FDOQ1003605
Authors: Amy Glen, J. Justin, Luca Q. Zamboni, Steven Widmer 
Publication date: 4 March 2009
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Abstract: In this paper, we study combinatorial and structural properties of a new class of finite and infinite words that are 'rich' in palindromes in the utmost sense. A characteristic property of so-called "rich words" is that all complete returns to any palindromic factor are themselves palindromes. These words encompass the well-known episturmian words, originally introduced by the second author together with X. Droubay and G. Pirillo in 2001. Other examples of rich words have appeared in many different contexts. Here we present the first unified approach to the study of this intriguing family of words. Amongst our main results, we give an explicit description of the periodic rich infinite words and show that the recurrent balanced rich infinite words coincide with the balanced episturmian words. We also consider two wider classes of infinite words, namely "weakly rich words" and almost rich words (both strictly contain all rich words, but neither one is contained in the other). In particular, we classify all recurrent balanced weakly rich words. As a consequence, we show that any such word on at least three letters is necessarily episturmian; hence weakly rich words obey Fraenkel's conjecture. Likewise, we prove that a certain class of almost rich words obeys Fraenkel's conjecture by showing that the recurrent balanced ones are episturmian or contain at least two distinct letters with the same frequency. Lastly, we study the action of morphisms on (almost) rich words with particular interest in morphisms that preserve (almost) richness. Such morphisms belong to the class of "P-morphisms" that was introduced by A. Hof, O. Knill, and B. Simon in 1995.
Full work available at URL: https://arxiv.org/abs/0801.1656
Recommendations
- Palindromic factorization of rich words
- Palindromic rich words and run-length encodings
- scientific article; zbMATH DE number 410195
- scientific article; zbMATH DE number 5726976
- scientific article; zbMATH DE number 2123889
- scientific article; zbMATH DE number 4164945
- Palindromic richness for languages invariant under more symmetries
- On highly palindromic words
- Palindromes: Density and Divisibility
Cites Work
- Balanced words
- Title not available (Why is that?)
- Sturmian words: structure, combinatorics, and their arithmetics
- Palindrome complexity.
- Singular continuous spectrum for palindromic Schrödinger operators
- Mirror substitutions and palindromic sequences
- Return words in Sturmian and episturmian words
- ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
- Episturmian words and some constructions of de Luca and Rauzy
- Substitution dynamical systems - spectral analysis
- Substitutions in dynamics, arithmetics and combinatorics
- Sturmian and Episturmian Words
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity and special factors
- Sequences with minimal block growth
- Episturmian words and episturmian morphisms
- Palindromes and Sturmian words
- Palindromic complexity of infinite words associated with simple Parry numbers
- Factor versus palindromic complexity of uniformly recurrent infinite words
- A connection between palindromic and factor complexity using return words
- Palindromic prefixes and Diophantine approximation
- COMBINATORIAL PROPERTIES OF ARNOUX–RAUZY SUBSHIFTS AND APPLICATIONS TO SCHRÖDINGER OPERATORS
- Episturmian words: a survey
- Palindromic prefixes and episturmian words
- Complementing and exactly covering sequences
- Descendants of primitive substitutions
- A characterization of balanced episturmian sequences
- Title not available (Why is that?)
Cited In (85)
- On highly palindromic words: the \(n\)-ary case
- Palindrome pattern matching
- Palindrome pattern matching
- On palindromic factorization of words
- On theta-palindromic richness
- Counting distinct palindromes in a word in linear time
- On Brlek-Reutenauer conjecture
- Balancing and clustering of words in the Burrows-Wheeler transform
- Extensions of rich words
- On a question of Hof, Knill and Simon on palindromic substitutive systems
- Palindromic complexity of codings of rotations
- On highly potential words
- Palindromic rich words and run-length encodings
- Rich, Sturmian, and trapezoidal words
- A counterexample to a question of Hof, Knill and Simon
- Palindromic prefixes and episturmian words
- Words with many palindrome pair factors
- On abelian saturated infinite words
- Infinite words with finite defect
- Special factors and the combinatorics of suffix and factor automata
- Infinite words rich and almost rich in generalized palindromes
- Upper bound for palindromic and factor complexity of rich words
- Sturmian jungle (or garden?) On multiliteral alphabets
- Codings of rotations on two intervals are full
- Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences
- Constructions of words rich in palindromes and pseudopalindromes
- A new characteristic property of rich words
- Algorithms and combinatorial properties on shortest unique palindromic substrings
- Palindromic factorization of rich words
- Repetitions in infinite palindrome-rich words
- Palindrome complexity.
- A connection between palindromic and factor complexity using return words
- Burrows-Wheeler transform and palindromic richness
- Rich and Periodic-Like Words
- A metric characterisation of repulsive tilings
- On generating binary words palindromically
- Generalized Thue-Morse words and palindromic richness
- On highly palindromic words: the ternary case
- On the least number of palindromes contained in an infinite word
- Generalized trapezoidal words
- Specular sets
- Title not available (Why is that?)
- Palindromic trees for a sliding window and its applications
- Rich square-free words
- Balanced Words Having Simple Burrows-Wheeler Transform
- Local symmetry dynamics in one-dimensional aperiodic lattices: a numerical study
- Morphic images of episturmian words having finite palindromic defect
- Palindromic sequences generated from marked morphisms
- Title not available (Why is that?)
- Privileged factors in the Thue-Morse word -- a comparison of privileged words and palindromes
- ALMOST RICH WORDS AS MORPHIC IMAGES OF RICH WORDS
- On the zero defect conjecture
- On Morphisms Preserving Palindromic Richness
- Episturmian words: a survey
- Introducing privileged words: privileged complexity of Sturmian words
- Languages invariant under more symmetries: overlapping factors versus palindromic richness
- A characterization of subshifts with bounded powers
- Palindromic richness for languages invariant under more symmetries
- Palindromic closures using multiple antimorphisms
- Finite and infinite closed-rich words
- Enumeration of two dimensional palindromes
- Computing longest single-arm-gapped palindromes in a string
- On closed-rich words
- Open and closed factors in Arnoux-Rauzy words
- On \(k\)-abelian palindromes
- Lambda words: a class of rich words defined over an infinite alphabet
- Specular sets
- Ostrowski-automatic sequences: theory and applications
- The sequence of open and closed prefixes of a Sturmian word
- On generalized highly potential words
- Improved estimates for the number of privileged words
- A characterization of Sturmian sequences by indistinguishable asymptotic pairs
- A unique extension of rich words
- Tight bound for the number of distinct palindromes in a tree
- Perfect balance and circularly rich words
- HV-Palindromes in Two-Dimensional Words
- Palindromic length of words and morphisms in class \(\mathcal{P}\)
- The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
- Efficient computation of longest single-arm-gapped palindromes in a string
- Rich words in the block reversal of a word
- The lexicographically least binary rich word achieving the repetition threshold
- Morphisms generating antipalindromic words
- The repetition threshold for binary rich words
- Counting palindromes in substrings
- Abelian combinatorics on words: a survey
This page was built for publication: Palindromic richness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1003605)
