Pseudoperiodic Words and a Question of Shevelev - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Preprints, Working Papers, ... Year : 2023

Pseudoperiodic Words and a Question of Shevelev

Abstract

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.
Fichier principal
Vignette du fichier
2207.10171.pdf (618.46 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03799690 , version 1 (17-10-2023)

Licence

Identifiers

Cite

Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, Sonja Linghui Shan. Pseudoperiodic Words and a Question of Shevelev. 2023. ⟨lirmm-03799690⟩
18 View
10 Download

Altmetric

Share

More