کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437552 | 690156 | 2011 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Return time complexity of Sturmian sequences
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let be the recurrence time of the initial n-word of an infinite sequence . We have that is periodic if and only if there exists M such that for all n>M. For non-periodic sequences, therefore, is the possible lowest upper bound for Rn. We show that if for all n, then is Sturmian. The opposite does not hold in general and we completely classify such Sturmian sequences.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 412, Issue 29, 1 July 2011, Pages 3413-3417
Journal: Theoretical Computer Science - Volume 412, Issue 29, 1 July 2011, Pages 3413-3417