2018/10/31 by Josef Rukavicka · 6 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Alphabet #Coding theory and cryptography #Combinatorics #DNA and Biological Computing #Geometry #Linguistics #Mathematical analysis #Mathematics #Palindrome #Philosophy #Physics #Upper and lower bounds #Word (group theory) #math.CO #msc:68R15 #semigroups and automata theory
paper · pdf · doi:10.1051/ita/2020008
published in RAIRO - Theoretical Informatics and Applications 55, 1 (EDP Sciences)
arxiv created 2019/10/23 · openalex publication_date 2021/01/01 · arxiv updated 2021/01/21 · openalex created_date 2021/02/01 · openalex updated_date 2026/08/05
A finite word w of length n contains at most n + 1 distinct palindromic factors. If the bound n + 1 is attained, the word w is called rich. An infinite word w is called rich if every finite factor of w is rich. Let w be a word (finite or infinite) over an alphabet with q > 1 letters, let Fac w ( n ) be the set of factors of length n of the word w , and let Pal w ( n ) ⊆ Fac w ( n ) be the set of palindromic factors of length n of the word w . We present several upper bounds for |Fac w ( n )| and |Pal w ( n )|, where w is a rich word. Let δ = [see formula in PDF]. In particular we show that |Fac w ( n )| ≤ (4 q 2 n ) δ ln 2 n +2 . In 2007, Baláži, Masáková, and Pelantová showed that |Pal w ( n )|+|Pal w ( n +1)| ≤ |Fac w ( n +1)|-|Fac w ( n )|+2, where w is an infinite word whose set of factors is closed under reversal. We prove this inequality for every finite word v with | v | ≥ n + 1 and v ( n + 1) closed under reversal.