solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看4611次
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 查看全文>>