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


