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.
2017
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]
File in questo prodotto:
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.

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