کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436997 690059 2012 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Characteristic Sturmian words are extremal for the Critical Factorization Theorem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Characteristic Sturmian words are extremal for the Critical Factorization Theorem
چکیده انگلیسی

We prove that characteristic Sturmian words are extremal for the Critical Factorization Theorem (CFT) in the following sense. If denotes the local period of an infinite word x at point n, we prove that x is a characteristic Sturmian word if and only if is smaller than or equal to n+1 for all n≥1 and it is equal to n+1 for infinitely many integers n.This result is extremal with respect to the CFT since a consequence of the CFT is that, for any infinite recurrent word x, either the function is bounded, and in such a case x is periodic, or for infinitely many integers n.As a byproduct of the techniques used in the paper we extend a result of Harju and Nowotka (2002) in [18] stating that any finite Fibonacci word , has only one critical point. Indeed we determine the exact number of critical points in any finite standard Sturmian word.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 454, 5 October 2012, Pages 199-205