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
11 h 00 min - 12 h 00 min

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



Retour en haut