We introduce and study natural derivatives for Christoffel and standard words, as well as for characteristic Sturmian words. These derivatives, which are defined as inverse images under suitable morphisms, preserve the aforementioned classes of words. In the case of Christoffel words, the morphisms involved map $a$ to $a^{k+1}b$ (resp., $ab^k$) and $b$ to $a^kb$ (resp.,$ab^{k+1}$) for a suitable $k>0$. As long as derivatives are not just a single letter, higher-order derivatives are naturally obtained. We define the depth of a Christoffel or of a standard word as the smallest order for which the derivative is a single letter. We give several combinatorial and arithmetic descriptions of the depth, and (tight) lower and upper bounds for it.
On Christoffel and standard words and their derivatives / D'Aniello, Alma; de Luca, Aldo; DE LUCA, Alessandro. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 658:(2017), pp. 122-147. [10.1016/j.tcs.2016.05.010]
On Christoffel and standard words and their derivatives
D'ANIELLO, ALMA;de Luca, Aldo;DE LUCA, ALESSANDRO
2017
Abstract
We introduce and study natural derivatives for Christoffel and standard words, as well as for characteristic Sturmian words. These derivatives, which are defined as inverse images under suitable morphisms, preserve the aforementioned classes of words. In the case of Christoffel words, the morphisms involved map $a$ to $a^{k+1}b$ (resp., $ab^k$) and $b$ to $a^kb$ (resp.,$ab^{k+1}$) for a suitable $k>0$. As long as derivatives are not just a single letter, higher-order derivatives are naturally obtained. We define the depth of a Christoffel or of a standard word as the smallest order for which the derivative is a single letter. We give several combinatorial and arithmetic descriptions of the depth, and (tight) lower and upper bounds for it.File | Dimensione | Formato | |
---|---|---|---|
OCaswatd.pdf
solo utenti autorizzati
Descrizione: Articolo
Tipologia:
Documento in Post-print
Licenza:
Accesso privato/ristretto
Dimensione
643.67 kB
Formato
Adobe PDF
|
643.67 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.