Joseph Meleshko;Pascal Ochem;Jeffrey Shallit;Sonja Linghui Shan
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.