Characteristic Sturmian words are extremal for the Critical Factorization Theorem

详细信息    查看全文

• 作者：Filippo Mignosi^a ; Antonio Restivo^b ; ^{restivo@math.unipa.it}
• 关键词：Combinatorics on words ; Periodicity ; Sturmian words ; Critical Factorization Theorem
• 刊名：Theoretical Computer Science
• 出版年：2012
• 出版时间：5 October, 2012
• 年：2012
• 卷：454
• 期：Complete
• 页码：199-205
• 全文大小：1K

文摘

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 , we prove that x is a characteristic Sturmian word if and only if is smaller than or equal to for all and it is equal to for infinitely many integers .

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 .

As a byproduct of the techniques used in the paper we extend a result of Harju and Nowotka (2002) in 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.