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

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