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.

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

RESTIVO, Antonio
2012-01-01

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.
2012
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 Dimensione Formato  
Critical Factorization_TCS2012.pdf

Solo gestori archvio

Dimensione 229.01 kB
Formato Adobe PDF
229.01 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/73702
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 4
social impact