Geodesic
Pseudoperiodic Words and a Question of Shevelev
Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 2.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.46298/dmtcs.9919
Classification : 68Rxx 
@article{DMTCS_2024_25_2_a10,
     author = {Meleshko, Joseph and Ochem, Pascal and Shallit, Jeffrey and Shan, Sonja Linghui},
     title = {Pseudoperiodic {Words} and a {Question} of {Shevelev}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {25},
     number = {2},
     year = {2023-2024},
     doi = {10.46298/dmtcs.9919},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9919/}
}
TY  - JOUR
AU  - Meleshko, Joseph
AU  - Ochem, Pascal
AU  - Shallit, Jeffrey
AU  - Shan, Sonja Linghui
TI  - Pseudoperiodic Words and a Question of Shevelev
JO  - Discrete mathematics & theoretical computer science
PY  - 2023-2024
VL  - 25
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9919/
DO  - 10.46298/dmtcs.9919
LA  - en
ID  - DMTCS_2024_25_2_a10
ER  - 
%0 Journal Article
%A Meleshko, Joseph
%A Ochem, Pascal
%A Shallit, Jeffrey
%A Shan, Sonja Linghui
%T Pseudoperiodic Words and a Question of Shevelev
%J Discrete mathematics & theoretical computer science
%D 2023-2024
%V 25
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9919/
%R 10.46298/dmtcs.9919
%G en
%F DMTCS_2024_25_2_a10
Meleshko, Joseph; Ochem, Pascal; Shallit, Jeffrey; Shan, Sonja Linghui. Pseudoperiodic Words and a Question of Shevelev. Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 2. doi : 10.46298/dmtcs.9919. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9919/

Cité par Sources :