6533b838fe1ef96bd12a3ea4

RESEARCH PRODUCT

Sturmian Graphs and a conjecture of Moser

Ilaria VenturiniChiara EpifanioJeffrey ShallitFilippo Mignosi

subject

Discrete mathematicsConjectureProperty (philosophy)Data structuresData structureCombinatoricsPhilosophy of languagecompressed suffixComputer Science::Discrete MathematicsContinued fractionComputer Science::Formal Languages and Automata TheoryAlgorithmsReal numberMathematics

description

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.

yearjournalcountryeditionlanguage
2004-01-01
10.1007/978-3-540-30550-7_15http://hdl.handle.net/10447/30284