2017/03/01 by Amihood Amir, Amir, Amihood, Costas S. Iliopoulos +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1703.00195
openalex publication_date 2017/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a generalization of a known fact from combinatorics on words related to periodicity into quasiperiodicity. 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.