کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436997 | 690059 | 2012 | 7 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 454, 5 October 2012, Pages 199-205