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 pseudoperiods 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.
翻译:我们将人们熟悉的周期性概念按顺序概括为一种新的假周期,并证明这方面的一些基本结果。我们重新审视2012年Shevelev文件的结果,以更简单、更统一的方式重新证实其结果,并完整地回答他以前尚未解决的问题之一。我们考虑用特定假周期和尽可能最小的关键提示来找到词语。最后,我们考虑确定一个限定词是否为一定大小的假周期的问题,并表明它是NP的完整。