Sturmian Graphs and a conjecture of Moser

Filippo Mignosi, Chiara Epifanio, Ilaria Venturini, Jeffrey Shallit

Risultato della ricerca: Other

4 Citazioni (Scopus)

Abstract

In this paper we define Sturmian graphs and we prove that all of them have a "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 CDAWGs of central Sturmian words. We show also that, analogously to the case of Sturmian words, these graphs converge to infinite ones.
Lingua originaleEnglish
Pagine175-187
Numero di pagine13
Stato di pubblicazionePublished - 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cita questo

Mignosi, F., Epifanio, C., Venturini, I., & Shallit, J. (2004). Sturmian Graphs and a conjecture of Moser. 175-187.

Sturmian Graphs and a conjecture of Moser. / Mignosi, Filippo; Epifanio, Chiara; Venturini, Ilaria; Shallit, Jeffrey.

2004. 175-187.

Risultato della ricerca: Other

Mignosi, F, Epifanio, C, Venturini, I & Shallit, J 2004, 'Sturmian Graphs and a conjecture of Moser', pagg. 175-187.
Mignosi, Filippo ; Epifanio, Chiara ; Venturini, Ilaria ; Shallit, Jeffrey. / Sturmian Graphs and a conjecture of Moser. 13 pag.
@conference{56520d8da4d348b5a59c96d0ce227b1c,
title = "Sturmian Graphs and a conjecture of Moser",
abstract = "In this paper we define Sturmian graphs and we prove that all of them have a {"}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 CDAWGs of central Sturmian words. We show also that, analogously to the case of Sturmian words, these graphs converge to infinite ones.",
author = "Filippo Mignosi and Chiara Epifanio and Ilaria Venturini and Jeffrey Shallit",
year = "2004",
language = "English",
pages = "175--187",

}

TY - CONF

T1 - Sturmian Graphs and a conjecture of Moser

AU - Mignosi, Filippo

AU - Epifanio, Chiara

AU - Venturini, Ilaria

AU - Shallit, Jeffrey

PY - 2004

Y1 - 2004

N2 - In this paper we define Sturmian graphs and we prove that all of them have a "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 CDAWGs of central Sturmian words. We show also that, analogously to the case of Sturmian words, these graphs converge to infinite ones.

AB - In this paper we define Sturmian graphs and we prove that all of them have a "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 CDAWGs of central Sturmian words. We show also that, analogously to the case of Sturmian words, these graphs converge to infinite ones.

UR - http://hdl.handle.net/10447/30284

M3 - Other

SP - 175

EP - 187

ER -