论文标题
伪造词和Shevelev的问题
Pseudoperiodic Words and a Question of Shevelev
论文作者
论文摘要
我们将序列中熟悉的周期性概念推广到一种新型的假性疾病，我们证明了一些基本结果。我们重新审视了2012年Shevelev论文的结果，并以更简单，更统一的方式谴责他的结果，并为他以前未解决的问题之一提供了完整的答案。我们考虑找到具有特定伪病的单词，并且具有最小的关键指数。最后，我们考虑确定有限词是否是给定尺寸的假性词的问题，并表明它是NP完整的。
We generalize the familiar notion of periodicity in sequences to a new kind of pseudoperiodicity, and we prove some basic results about it. We revisit the results of a 2012 paper of Shevelev and reprove his results in a simpler and more unified manner, and provide a complete answer to one of his previously unresolved questions. We consider finding words with specific pseudoperiod and having the smallest possible critical exponent. Finally, we consider the problem of determining whether a finite word is pseudoperiodic of a given size, and show that it is NP-complete.
