Pseudoperiodic Words and a Question of Shevelev

We generalize the familiar notion of periodicity in sequences to a new kindof pseudoperiodicity, and we prove some basic results about it. We revisit theresults of a 2012 paper of Shevelev and reprove his results in a simpler andmore unified manner, and provide a complete answer to one of his previouslyunresolved questions. We consider finding words with specific pseudoperiod andhaving the smallest possible critical exponent. Finally, we consider theproblem of determining whether a finite word is pseudoperiodic of a given size,and show that it is NP-complete