论文标题
封闭式和特权单词数量的渐近界限
Asymptotic bounds for the number of closed and privileged words
论文作者
论文摘要
如果$ u $是$ u $的非空格前缀和后缀，则一个单词〜$ w $具有边框$ u $。如果$ w $最多的$ 1 $，或者如果$ w $具有$ w $两次的边框，则据说〜$ w $是\ emph {闭合}。如果$ w $最多的$ 1 $，或者$ w $具有特权边框，则据说是\ emph {特权}单词〜$ w $，{特权} {特权}，而在$ w $中恰好发生了两次。令$ c_k（n）$（分别〜$ p_k（n）$）为长度 - $ n $ lengus-n $闭合（分别特权）字母上的单词。在本文中，我们改善了$ C_K（n）$和$ p_k（n）$的上限和下限。我们完全解决了$ C_K（N）$的渐近行为。我们还几乎可以通过给予一个被任意生长的因素分离的上限和下限的家庭来完全解决$ p_k（n）$的渐近行为。
A word~$w$ has a border $u$ if $u$ is a non-empty proper prefix and suffix of $u$. A word~$w$ is said to be \emph{closed} if $w$ is of length at most $1$ or if $w$ has a border that occurs exactly twice in $w$. A word~$w$ is said to be \emph{privileged} if $w$ is of length at most $1$ or if $w$ has a privileged border that occurs exactly twice in $w$. Let $C_k(n)$ (resp.~$P_k(n)$) be the number of length-$n$ closed (resp. privileged) words over a $k$-letter alphabet. In this paper, we improve existing upper and lower bounds on $C_k(n)$ and $P_k(n)$. We completely resolve the asymptotic behaviour of $C_k(n)$. We also nearly completely resolve the asymptotic behaviour of $P_k(n)$ by giving a family of upper and lower bounds that are separated by a factor that grows arbitrarily slowly.
