In this paper we define Sturmian graphs and we prove that all of them have a certain ''''counting'''' property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones.

EPIFANIO C, F MIGNOSI, J SHALLIT, I VENTURINI (2007). On Sturmian Graphs. DISCRETE APPLIED MATHEMATICS, 155(8), 1014-1030 [10.1016/j.dam.2006.11.003].

On Sturmian Graphs

EPIFANIO, Chiara;MIGNOSI, Filippo;
2007-01-01

Abstract

In this paper we define Sturmian graphs and we prove that all of them have a certain ''''counting'''' property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones.
2007
EPIFANIO C, F MIGNOSI, J SHALLIT, I VENTURINI (2007). On Sturmian Graphs. DISCRETE APPLIED MATHEMATICS, 155(8), 1014-1030 [10.1016/j.dam.2006.11.003].
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0166218X06004963-main.pdf

accesso aperto

Dimensione 261.57 kB
Formato Adobe PDF
261.57 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/10447/14526
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 6
social impact