EUVIMEDEUVIMED entdecken
Crossref

Pseudoperiodic Words and a Question of Shevelev

Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, Sonja Linghui Shan

Discrete Mathematics & Theoretical Computer Science · 16.10.2023 · vol. 25:2 (Automata, Logic and Semantics)

DOI: 10.46298/dmtcs.9919 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 16.10.2023. Verfasst von Joseph Meleshko und 3 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Meleshko, J., Ochem, P., Shallit, J., & Shan, S. L. (2023). Pseudoperiodic Words and a Question of Shevelev. Discrete Mathematics & Theoretical Computer Science, vol. 25:2(Automata, Logic and Semantics). https://doi.org/10.46298/dmtcs.9919

Vancouver

Meleshko J, Ochem P, Shallit J, Shan SL. Pseudoperiodic Words and a Question of Shevelev. Discrete Mathematics & Theoretical Computer Science. 2023;vol. 25:2(Automata, Logic and Semantics). doi:10.46298/dmtcs.9919

BibTeX
@article{Meleshko2023,
  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},
  year = {2023},
  volume = {vol. 25:2},
  number = {Automata, Logic and Semantics},
  doi = {10.46298/dmtcs.9919}
}
Kostenlos starten →