Joseph Meleshko ; Pascal Ochem ; Jeffrey Shallit ; Sonja Linghui Shan - Pseudoperiodic Words and a Question of Shevelev

dmtcs:9919 - Discrete Mathematics & Theoretical Computer Science, October 16, 2023, vol. 25:2 - https://doi.org/10.46298/dmtcs.9919
Pseudoperiodic Words and a Question of ShevelevArticle

Authors: 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.

    https://doi.org/10.46298/dmtcs.9919
    Source: arXiv.org:2207.10171
    Volume: vol. 25:2
    Section: Automata, Logic and Semantics
    Published on: October 16, 2023
    Accepted on: May 26, 2023
    Submitted on: August 15, 2022
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,Computer Science - Formal Languages and Automata Theory
    Licence: Attribution 4.0 International (CC BY 4.0)
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    Share and export

    Consultation statistics

    This page has been seen 566 times.
    This article's PDF has been downloaded 387 times.