Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Two strings at Hamming distance 1 cannot be both quasiperiodic

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:24:21Z
dc.abstract.enWe present a generalization to quasiperiodicity of a known fact from combinatorics on words related to periodicity. A string is called periodic if it has a period which is at most half of its length. A string w is called quasiperiodic if it has a non-trivial cover, that is, there exists a string c that is shorter than w and such that every position in w is inside one of the occurrences of c in w. It is a folklore fact that two strings that differ at exactly one position cannot be both periodic. Here we prove a more general fact that two strings that differ at exactly one position cannot be both quasiperiodic. Along the way we obtain new insights into combinatorics of quasiperiodicities.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorAmir, Amihood
dc.contributor.authorIliopoulos, Costas S.
dc.contributor.authorRadoszewski, Jakub
dc.date.accessioned2024-01-26T11:09:14Z
dc.date.available2024-01-26T11:09:14Z
dc.date.issued2017
dc.description.financeNie dotyczy
dc.description.volume128
dc.identifier.doi10.1016/J.IPL.2017.08.005
dc.identifier.issn0020-0190
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/123978
dc.identifier.weblinkhttps://www.sciencedirect.com/science/article/pii/S0020019017301473?via%3Dihub
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofInformation Processing Letters
dc.relation.pages54-57
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enCombinatorial problems
dc.subject.enCombinatorics on words
dc.subject.enQuasiperiodicity
dc.subject.enCover
dc.subject.enSeed
dc.titleTwo strings at Hamming distance 1 cannot be both quasiperiodic
dc.typeJournalArticle
dspace.entity.typePublication