Palindromic richness

Autor: Jacques Justin, Steve Widmer, Amy Glen, Luca Q. Zamboni
Přispěvatelé: Department of Mathematics and Statistics [Perth], Murdoch University, Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Jean Monnet [Saint-Étienne] (UJM)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Zamboni, Luca Q.
Rok vydání: 2009
Předmět:
FOS: Computer and information sciences
Class (set theory)
Discrete Mathematics (cs.DM)
0102 computer and information sciences
68R15
01 natural sciences
Theoretical Computer Science
Combinatorics
symbols.namesake
chemistry.chemical_compound
Morphism
Computer Science::Discrete Mathematics
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
0101 mathematics
ComputingMilieux_MISCELLANEOUS
Mathematics
Conjecture
010102 general mathematics
Palindrome
Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
chemistry
Computational Theory and Mathematics
010201 computation theory & mathematics
symbols
Combinatorics (math.CO)
Geometry and Topology
Characteristic property
Schrödinger's cat
Word (group theory)
Computer Science::Formal Languages and Automata Theory
Computer Science - Discrete Mathematics
Zdroj: European Journal of Combinatorics
European Journal of Combinatorics, Elsevier, 2009, 30, pp.510--531
ISSN: 0195-6698
1095-9971
DOI: 10.1016/j.ejc.2008.04.006
Popis: 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.
26 pages; merged with work of Steve Widmer and Luca Q. Zamboni on weakly rich words; accepted by the European Journal of Combinatorics
Databáze: OpenAIRE
Externí odkaz: