论文标题
特权单词数量的上限
Upper bound for the number of privileged words
论文作者
论文摘要
如果$ \ vert w \ vert <\ vert u \ vert $和$ w $是$ u $的一个非空词$ w $是一个单词$ u $的a \ emph {border}，既是前缀又是$ u $的后缀。如果$ \ vert u \ vert \ leq 1 $或$ u $具有特权边框$ w $，则单词$ u $是\ emph {privileged}，如果$ u $在$ u $中出现了两次。 Peltomäki（2016）提出了以下开放问题：``给出$ b（n）$''的非平凡的上限，其中$ b（n）$表示长度$ n $的特权单词数量。 令$ \ ln^{[0]} {（n）} = n $，然后让$ \ ln^{[[j]} {（n）} = \ ln {（\ ln^{[j-1]} {[J-1]} {（n）}} $，其中$ j，n $是正整数。我们表明，如果$ q> 1 $是字母的大小，而$ j \ geq 3 $是整数，那么有常数$α_j$和$ n_j $，这样就可以\ [b（n）\ leq α_j\ frac {q^{n} \ sqrt {\ ln {n}}}}} {\ sqrt {n}}} \ ln^{[j]} {（n）} \ prod_ {i = 2}^{j-1} \ sqrt {\ ln^{[i]}（n）} \ mbox {，其中} n \ geq n_j \ mbox {。} \]此结果改善了Rukavicka的上限（2020）。
A non-empty word $w$ is a \emph{border} of a word $u$ if $\vert w\vert<\vert u\vert$ and $w$ is both a prefix and a suffix of $u$. A word $u$ is \emph{privileged} if $\vert u\vert\leq 1$ or if $u$ has a privileged border $w$ that appears exactly twice in $u$. Peltomäki (2016) presented the following open problem: ``Give a nontrivial upper bound for $B(n)$'', where $B(n)$ denotes the number of privileged words of length $n$. Let $\ln^{[0]}{(n)}=n$ and let $\ln^{[j]}{(n)}=\ln{(\ln^{[j-1]}{(n)})}$, where $j,n$ are positive integers. We show that if $q>1$ is a size of the alphabet and $j\geq 3$ is an integer then there are constants $α_j$ and $n_j$ such that \[B(n)\leq α_j\frac{q^{n}\sqrt{\ln{n}}}{\sqrt{n}}\ln^{[j]}{(n)}\prod_{i=2}^{j-1}\sqrt{\ln^{[i]}(n)}\mbox{, where }n\geq n_j\mbox{.}\] This result improves the upper bound of Rukavicka (2020).
