论文标题
带有许多周期性的单词的单词长度
Palindromic Length of Words with Many Periodic Palindromes
论文作者
论文摘要
有限单词$ v $的palindromic长度$ \ text {pl}（v）$是串联等于$ v $的palindromes的最小数量。 2013年，Frid，Puzynina和Zamboni猜想：如果$ W $是无限的单词，而$ k $是一个整数，以至于$ \ text {pl}（u）\ leq k $对于$ w $ of $ w $ of $ w $，那么$ w $，那么$ w $最终是定期的。 假设$ w $是一个无限的单词，$ k $是整数这样的$ \ text {pl}（u）\ leq k $，对于每个因素$ u $ of $ w $。令$ω（w，k）$是所有因素的集合$ u $ $ w $，其具有超过$ \ sqrt [k] {k^{ - 1} \ vert u \ vert} $ palindromic prefixes。我们表明$ω（w，k）$是无限的套装，我们表明，对于每个正整数$ j $，都有palindromes $ a，b $和w $ u \ inω（w，k）$，因此$（ab）^j $是$ u $ $ $ $，$ b $的一个因素。请注意，$（ab）^j $是一个周期性的单词，$（ab）^ia $是每个$ i \ leq j $的回文。这些结果证明了以下问题的合理性：$ b $的后缀和定期单词$（AB）^j $的后缀的列表长度是多少？ 众所周知，$ \ lvert \ text {pl}（uv） - \ text {pl}（u）\ rvert \ leq \ leq \ text {pl}（v）$，其中$ u $ and $ v $是非空的单词。我们文章的主要结果表明，如果$ a，b $是palindromes，$ b $是非exprenty，$ u $是$ b $的非空后缀，$ \ vert ab \ vert $是$ aba $的最低时期，$ j $是带有$ j \ geq3 \ geq3 \ pl {pl {pl}（u）的正整数，那么$ \ text {pl}（u（ab）^j） - \ text {pl}（u）\ geq 0 $。
The palindromic length $\text{PL}(v)$ of a finite word $v$ is the minimal number of palindromes whose concatenation is equal to $v$. In 2013, Frid, Puzynina, and Zamboni conjectured that: If $w$ is an infinite word and $k$ is an integer such that $\text{PL}(u)\leq k$ for every factor $u$ of $w$ then $w$ is ultimately periodic. Suppose that $w$ is an infinite word and $k$ is an integer such $\text{PL}(u)\leq k$ for every factor $u$ of $w$. Let $Ω(w,k)$ be the set of all factors $u$ of $w$ that have more than $\sqrt[k]{k^{-1}\vert u\vert}$ palindromic prefixes. We show that $Ω(w,k)$ is an infinite set and we show that for each positive integer $j$ there are palindromes $a,b$ and a word $u\in Ω(w,k)$ such that $(ab)^j$ is a factor of $u$ and $b$ is nonempty. Note that $(ab)^j$ is a periodic word and $(ab)^ia$ is a palindrome for each $i\leq j$. These results justify the following question: What is the palindromic length of a concatenation of a suffix of $b$ and a periodic word $(ab)^j$ with "many" periodic palindromes? It is known that $\lvert\text{PL}(uv)-\text{PL}(u)\rvert\leq \text{PL}(v)$, where $u$ and $v$ are nonempty words. The main result of our article shows that if $a,b$ are palindromes, $b$ is nonempty, $u$ is a nonempty suffix of $b$, $\vert ab\vert$ is the minimal period of $aba$, and $j$ is a positive integer with $j\geq3\text{PL}(u)$ then $\text{PL}(u(ab)^j)-\text{PL}(u)\geq 0$.
