Name
Abstract | ||
|---|---|---|
We prove that characteristic Sturmian words are extremal for the Critical Factorization Theorem (CFT) in the following sense. If p"x(n) 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 p"x(n) 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 p"x is bounded, and in such a case x is periodic, or p"x(n)=n+1 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 f"n,n=5, has only one critical point. Indeed we determine the exact number of critical points in any finite standard Sturmian word. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.tcs.2012.03.012 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
infinite word,characteristic Sturmian word,point n,Critical Factorization Theorem,integers n,Characteristic Sturmian word,function p,finite standard Sturmian word,finite Fibonacci word,infinite recurrent word,critical point | Journal | 454, |
ISSN | Citations | PageRank |
0304-3975 | 6 | 0.64 |
References | Authors | |
11 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Filippo Mignosi | 1 | 569 | 99.71 |
| Antonio Restivo | 2 | 697 | 107.05 |