We define a family of natural decompositions of Sturmian words in Christoffel words, called reversible Christoffel (RC) factorizations. They arise from the observation that two Sturmian words with the same language have (almost always) arbitrarily long Abelian equivalent prefixes. Using the three gap theorem, we prove that in each RC factorization, only 2 or 3 distinct Christoffel words may occur. We begin the study of such factorizations, considered as infinite words over 2 or 3 letters, and show that in the general case they are either Sturmian words, or obtained by a three-interval exchange transformation.

Reversible Christoffel factorizations / Michelangelo, Bucci; DE LUCA, Alessandro; Luca Q., Zamboni. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 495:(2013), pp. 17-24. [10.1016/j.tcs.2013.05.042]

Reversible Christoffel factorizations

DE LUCA, ALESSANDRO
;
2013

Abstract

We define a family of natural decompositions of Sturmian words in Christoffel words, called reversible Christoffel (RC) factorizations. They arise from the observation that two Sturmian words with the same language have (almost always) arbitrarily long Abelian equivalent prefixes. Using the three gap theorem, we prove that in each RC factorization, only 2 or 3 distinct Christoffel words may occur. We begin the study of such factorizations, considered as infinite words over 2 or 3 letters, and show that in the general case they are either Sturmian words, or obtained by a three-interval exchange transformation.
2013
Reversible Christoffel factorizations / Michelangelo, Bucci; DE LUCA, Alessandro; Luca Q., Zamboni. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 495:(2013), pp. 17-24. [10.1016/j.tcs.2013.05.042]
File in questo prodotto:
File Dimensione Formato  
1211.3049.pdf

Open Access dal 16/07/2015

Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 124.25 kB
Formato Adobe PDF
124.25 kB Adobe PDF Visualizza/Apri

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/11588/567528
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact