Artykuł w czasopiśmie
Brak miniatury
Licencja

ClosedAccessDostęp zamknięty

Two strings at Hamming distance 1 cannot be both quasiperiodic

Autor
Amir, Amihood
Iliopoulos, Costas S.
Radoszewski, Jakub
Data publikacji
2017
Abstrakt (EN)

We 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.

Słowa kluczowe EN
Combinatorial problems
Combinatorics on words
Quasiperiodicity
Cover
Seed
Dyscyplina PBN
informatyka
Czasopismo
Information Processing Letters
Tom
128
Strony od-do
54-57
ISSN
0020-0190
Licencja otwartego dostępu
Dostęp zamknięty