Pseudoperiodic Words and a Question of Shevelev
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 pre...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-10-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/9919/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850278338418966528 |
|---|---|
| author | Joseph Meleshko Pascal Ochem Jeffrey Shallit Sonja Linghui Shan |
| author_facet | Joseph Meleshko Pascal Ochem Jeffrey Shallit Sonja Linghui Shan |
| author_sort | Joseph Meleshko |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-95a9b9f94eb54458bd28dcee33849067 |
| institution | OA Journals |
| issn | 1365-8050 |
| language | English |
| publishDate | 2023-10-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-95a9b9f94eb54458bd28dcee338490672025-08-20T01:49:32ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-10-01vol. 25:2Automata, Logic and Semantics10.46298/dmtcs.99199919Pseudoperiodic Words and a Question of ShevelevJoseph MeleshkoPascal OchemJeffrey ShallitSonja Linghui ShanWe 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.http://dmtcs.episciences.org/9919/pdfmathematics - combinatoricscomputer science - discrete mathematicscomputer science - formal languages and automata theory |
| spellingShingle | Joseph Meleshko Pascal Ochem Jeffrey Shallit Sonja Linghui Shan Pseudoperiodic Words and a Question of Shevelev Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics computer science - discrete mathematics computer science - formal languages and automata theory |
| title | Pseudoperiodic Words and a Question of Shevelev |
| title_full | Pseudoperiodic Words and a Question of Shevelev |
| title_fullStr | Pseudoperiodic Words and a Question of Shevelev |
| title_full_unstemmed | Pseudoperiodic Words and a Question of Shevelev |
| title_short | Pseudoperiodic Words and a Question of Shevelev |
| title_sort | pseudoperiodic words and a question of shevelev |
| topic | mathematics - combinatorics computer science - discrete mathematics computer science - formal languages and automata theory |
| url | http://dmtcs.episciences.org/9919/pdf |
| work_keys_str_mv | AT josephmeleshko pseudoperiodicwordsandaquestionofshevelev AT pascalochem pseudoperiodicwordsandaquestionofshevelev AT jeffreyshallit pseudoperiodicwordsandaquestionofshevelev AT sonjalinghuishan pseudoperiodicwordsandaquestionofshevelev |