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  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.

Mignosi, F., & Restivo, A. (2012). Characteristic Sturmian words are extremal for the Critical Factorization Theorem. THEORETICAL COMPUTER SCIENCE, 454, 199-205 [10.1016/j.tcs.2012.03.012].

### Characteristic Sturmian words are extremal for the Critical Factorization Theorem

#### 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  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.
##### Scheda breve Scheda completa Scheda completa (DC) Settore INF/01 - Informatica
Mignosi, F., & Restivo, A. (2012). Characteristic Sturmian words are extremal for the Critical Factorization Theorem. THEORETICAL COMPUTER SCIENCE, 454, 199-205 [10.1016/j.tcs.2012.03.012].
File in questo prodotto:
File
Critical Factorization_TCS2012.pdf

Solo gestori archvio

Dimensione 229.01 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `http://hdl.handle.net/10447/73702`
• ND
• 7
• 4