solidot新版网站常见问题,请点击这里查看。

An Upper Bound for Palindromic and Factor Complexity of Rich Words. (arXiv:1810.03573v1 [math.CO])

来源于:arXiv
A finite word $w$ of length $n$ contains at most $n+1$ distinct palindromic factors. If the bound $n+1$ is reached, 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 rich 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 show that $\vert F_p(w,n)\vert\leq (q+1)n(4q^{10}n)^{\log_2{n}}$ and $\vert F(w,n)\vert \leq (q+1)^2n^4(4q^{10}n)^{2\log_2{n}}$. It is known that $\vert F_p(w,n)\vert +\vert F_p(w,n+1)\vert \leq \vert F(w,n+1)\vert-\vert F(w,n)\vert+2$, where $w$ is an infinite word closed under reversal [Bal\'a\v{z}i, Mas\'akov\'a, Pelantov\'a, Theor. Comput. Sci., 380 (2007)]. We generalize this inequality for finite words and consequently we derive that $\vert F(w,n)\vert \leq 2(n-1)\hat F_p(w,n)-2(n-1) +q$ and $\vert F(w,n)\vert \leq 2 查看全文>>