Upper Bound for Palindromic and Factor Complexity of Rich Words

Abstract

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 $F(w,n)$ be the set of factors of length $n$ of the word $w$, and let $F_p(w,n)\subseteq F(w,n)$ be the set of palindromic factors of length $n$ of the word $w$. We present several upper bounds for $|F(w,n)|$ and $|F_p(w,n)|$, where $w$ is a rich word. In particular we show that \[| F(w,n)| \leq (q+1)8n^2(8q^{10}n)^{\log_2{2n}}+q\mbox{.}\] In 2007, Bal{á}{\v z}i, Mas{á}kov{á}, and Pelantov{á} showed that \[| F_p(w,n)| +| F_p(w,n+1)| \leq | F(w,n+1)|-| F(w,n)|+2\mbox{,}\] where $w$ is an infinite word whose set of factors is closed under reversal. We generalize this inequality for finite words.

References in corpus (10)

• Palindromic Richness
• A connection between palindromic and factor complexity using return words
• A new characteristic property of rich words
• On the Combinatorics of Palindromes and Antipalindromes
• Subword complexity and power avoidance
• Extensions of rich words
• The Number of Distinct Subpalindromes in Random Words
• On Number of Rich Words
• On Words with the Zero Palindromic Defect
• Transition Property for $\alpha$-Power Free Languages with $\alpha \ge 2$ and $k\ge 3$ Letters

Cited by in corpus (3)

• A Unique Extension of Rich Words
• Palindromic factorization of rich words
• Construction Of A Rich Word Containing Given Two Factors