Un algorithme de fractions continues bidimensionnelles produisant des mots de complexité 2n+1
Julien Cassaigne
I2M, CNRS, Marseille
/user/julien.cassaigne/
Date(s) : 15/11/2016 iCal
11h00 - 12h00
Un algorithme de fractions continues 2D peut être vu comme un moyen, à partir d’un triplet (x, y, z) de somme 1, de construire par un procédé s-adique un mot infini ternaire dont les fréquences sont précisément x, y, et z. L’algorithme d’Arnoux-Rauzy donne les mots les plus simples, de complexité 2n+1, mais il a le défaut de n’être défini que sur un ensemble de mesure nulle (la baderne de Rauzy).
Nous présentons un nouvel algorithme, obtenu à partir de l’analyse des graphes de Rauzy et de leur évolution, qui produit des mots de complexité 2n+1 pour tout triplet de fréquences. Nous discutons ses liens avec l’algorithme de Selmer, et la difficulté à le généraliser en dimension supérieure.
An algorithm of two-dimensional continued fractions producing words of complexity 2n + 1
A 2D continued fraction algorithm can be seen as a way, from a triplet (x, y, z) of sum 1, to construct by an s-adic process a ternary infinite word whose frequencies are precisely x, y , and z. The Arnoux-Rauzy algorithm gives the simplest words, of complexity 2n+1, but it has the defect of only being defined on a set of zero measure (Rauzy’s baderne).
We present a new algorithm, obtained from the analysis of Rauzy graphs and their evolution, which produces words of complexity 2n + 1 for any triplet of frequencies. We discuss its links with Selmer’s algorithm, and the difficulty in generalizing it in higher dimensions.
https://arxiv.org/abs/1707.02741
Catégories
