Sur la complexité conjecturée de la suite d’Oldenburger-Kolakoski
Date(s) : 30/05/2023 iCal
11h00 - 12h00
La suite d'(Oldenburger-)Kolakoski est la suite 𝐾, à valeurs dans {1, 2}, telle que 𝐾𝑛 est la longueur du 𝑛-ème bloc de symboles identiques dans 𝐾. Dekking a conjecturé en 1981 que sa fonction de complexité 𝑝𝐾(𝑛), qui compte le nombre de mots finis de longueur 𝑛 dans 𝐾, vérifiait 𝑝𝐾(𝑛)=Θ(𝑛ρ), avec ρ=log(3)/log(3/2). Nous prouvons, sous l’hypothèse que l’ensemble des facteurs de 𝐾 est invariant par l’échange de 1 et 2, que 𝑝(𝑛)=Ω(𝑛ρ), et, sous l’hypothèse que 1 et 2 apparaissent dans 𝐾 avec la fréquence 1/2 (un problème ouvert notoire), que 𝑝(𝑛)=O(𝑛ρ+ε) pour tout ε>0. Enfin, sous des hypothèses un peu plus fortes, nous obtenons un équivalent plus précis que la conjecture de Dekking.
Emplacement
I2M Luminy - Ancienne BU, Salle Séminaire2 (RdC)
Catégories
