On Sturmian Graphs

Filippo Mignosi, Chiara Epifanio, Ilaria Venturini, Filippo Mignosi, Jeffrey Shallit

Risultato della ricerca: Article

6 Citazioni (Scopus)

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.
Lingua originaleEnglish
pagine (da-a)1014-1030
Numero di pagine17
RivistaDiscrete Applied Mathematics
Volume155
Stato di pubblicazionePublished - 2007

Fingerprint

Sturmian Words
Graph in graph theory
Counting
Continued Fraction Expansion
Analogy
Converge

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cita questo

Mignosi, F., Epifanio, C., Venturini, I., Mignosi, F., & Shallit, J. (2007). On Sturmian Graphs. Discrete Applied Mathematics, 155, 1014-1030.

On Sturmian Graphs. / Mignosi, Filippo; Epifanio, Chiara; Venturini, Ilaria; Mignosi, Filippo; Shallit, Jeffrey.

In: Discrete Applied Mathematics, Vol. 155, 2007, pag. 1014-1030.

Risultato della ricerca: Article

Mignosi, F, Epifanio, C, Venturini, I, Mignosi, F & Shallit, J 2007, 'On Sturmian Graphs', Discrete Applied Mathematics, vol. 155, pagg. 1014-1030.
Mignosi F, Epifanio C, Venturini I, Mignosi F, Shallit J. On Sturmian Graphs. Discrete Applied Mathematics. 2007;155:1014-1030.
Mignosi, Filippo ; Epifanio, Chiara ; Venturini, Ilaria ; Mignosi, Filippo ; Shallit, Jeffrey. / On Sturmian Graphs. In: Discrete Applied Mathematics. 2007 ; Vol. 155. pagg. 1014-1030.
@article{0548a6d78b1c43948ba95ba2a0850c7f,
title = "On Sturmian Graphs",
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.",
author = "Filippo Mignosi and Chiara Epifanio and Ilaria Venturini and Filippo Mignosi and Jeffrey Shallit",
year = "2007",
language = "English",
volume = "155",
pages = "1014--1030",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

TY - JOUR

T1 - On Sturmian Graphs

AU - Mignosi, Filippo

AU - Epifanio, Chiara

AU - Venturini, Ilaria

AU - Mignosi, Filippo

AU - Shallit, Jeffrey

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

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

M3 - Article

VL - 155

SP - 1014

EP - 1030

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -