0000000000611637

AUTHOR

Ilaria Venturini

showing 2 related works from this author

On Sturmian Graphs

2007

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

Discrete mathematicsApplied MathematicsCDAWGsContinued fractionsSturmian wordSturmian wordsCharacterization (mathematics)RepeatsDirected acyclic graphCombinatoricsIndifference graphSturmian words CDAWGs Continued fractions RepeatsChordal graphComputer Science::Discrete MathematicsDiscrete Mathematics and CombinatoricsContinued fractionWord (group theory)Computer Science::Formal Languages and Automata TheoryReal numberMathematics
researchProduct

Sturmian Graphs and a conjecture of Moser

2004

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.

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