2008/07/15 by Michelangelo Bucci, Alessandro De Luca, Amy Glen +1 · 37 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Artificial intelligence #Biology #Class (philosophy) #Combinatorics #Computer science #Linguistics #Mathematics #Natural Language Processing Techniques #Palindrome #Philosophy #Prefix #Property (philosophy) #Pure mathematics #Suffix #cs.DM #math.CO #msc:68R15 #semigroups and automata theory
paper · pdf · doi:10.1016/j.tcs.2008.11.001
published in Theoretical Computer Science 410(30-32), 2860-2863 (Elsevier BV) · 6 pages
arxiv created 2008/07/15 · openalex publication_date 2008/11/26 · arxiv updated 2010/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Originally introduced and studied by the third and fourth authors together with J. Justin and S. Widmer in arXiv:0801.1656, rich words constitute a new class of finite and infinite words characterized by containing the maximal number of distinct palindromes. Several characterizations of rich words have already been established. A particularly nice characteristic property is that all 'complete returns' to palindromes are palindromes. In this note, we prove that rich words are also characterized by the property that each factor is uniquely determined by its longest palindromic prefix and its longest palindromic suffix.