Sturmian Graphs and a conjecture of Moser

Filippo Mignosi, Chiara Epifanio, Ilaria Venturini, Jeffrey Shallit

Research output: Contribution to conferenceOtherpeer-review

4 Citations (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.
Original languageEnglish
Pages175-187
Number of pages13
Publication statusPublished - 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Sturmian Graphs and a conjecture of Moser'. Together they form a unique fingerprint.

Cite this