کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950855 | 1441034 | 2017 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Two strings at Hamming distance 1 cannot be both quasiperiodic
ترجمه فارسی عنوان
دو رشته در فاصله 1 هاممگین نمی توانند هر دو دوره ای باشند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکلات ترکیبی ترکیبیات بر روی کلمات، زودگذر بودن، پوشش دادن، بذر
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 128, December 2017, Pages 54-57
Journal: Information Processing Letters - Volume 128, December 2017, Pages 54-57
نویسندگان
Amihood Amir, Costas S. Iliopoulos, Jakub Radoszewski,