کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950000 | 1440209 | 2016 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The New Periodicity Lemma revisited
ترجمه فارسی عنوان
لمس دوره ای جدید بازمیگردد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رشته، مربع، تخمین کانونیکس، مربع دو لمس دوره ای جدید،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In 2006, the New Periodicity Lemma (NPL) was published, showing that the occurrence of two squares starting at a position i in a string necessarily precludes the occurrence of other squares of specified period in a specified neighbourhood of i. The proof of this lemma was complex, breaking down into 14 subcases, and requiring that the shorter of the two squares be regular. In this paper we significantly relax the conditions required by the NPL and removing the need for regularity altogether, and we establish a more precise result using a simpler proof based on lemmas that expose new combinatorial structures in a string, in particular a canonical factorization for any two squares that start at the same position.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 212, 30 October 2016, Pages 30-36
Journal: Discrete Applied Mathematics - Volume 212, 30 October 2016, Pages 30-36
نویسندگان
Haoyue Bai, Frantisek Franek, William F. Smyth,