Conjecture de Billaud

La conjecture de Billaud est une conjecture en combinatoire des mots, formulée par Michel Billaud, qui concerne une propriété qu'un mot vérifie s'il en est ainsi pour ses sous-mots obtenus en effaçant toutes les occurrences d'une lettre.

Énoncé

La conjecture de Billaud est la suivante : Modèle:Théorème La conjecture a été formulée en 1993 et est encore ouverte en 2022.

Résultats partiels

La conjecture est trivialement vérifiée pour un alphabet à 2 lettres, et a été démontrée par P. Zimmermann « A problem with words from Michel Billaud » pour un alphabet à 3 trois lettres. Françoise Levé et Gwénaël Richomme ont démontré la conjecture dans le cas où chaque morphisme $f_x$ de l'énoncé n'a qu'une seule lettre expansive (une lettre $a$ est dite expansive pour un morphisme $h$ si $a$ figure dans l'image $h(a)$ et si $h(a)$ est de longueur au moins 2). La conjecture a été prouvée pour un alphabet à 4 lettres.

Exemple

On considère le morphisme $f$ sur $\{1,2,3,4,5,6,7,8,9\}$ donné par

$f(1)=2$, $f(2)=1$, $f(3)=34$, $f(4)=435$, $f(5)=6$, $f(6)=7$, $f(7)=\epsilon$, $f(8)=6787$, $f(9)=966$.

Les lettres mortelles sont $\{5,6,7\}$, les lettres expansives sont $\{8,9\}$. Les points fixes de $f$ sont les mots de $\{76787,96677{\}}^{*}$ puisque en effet par exemple

$f(76787)=\epsilon \cdot 7\cdot \epsilon \cdot 6787\cdot \epsilon$.

On note FW l'ensemble des mots qui sont points fixes d'un morphisme non trivial

$\mathrm{F}\mathrm{W}=\{w\mid \mathrm{\exists }f\ne \mathrm{I}\mathrm{d}:f(w)=w\}$.

Un témoin pour un mot $w$ dans FW est un morphisme $f$ non trivial tel que $f(w)=w$. Enfin, on note ${\delta }_x(w)$ le mot obtenu en effaçant toutes les occurrences de la lettre $x$ dans $w$. Un tel mot est un héritier (heir en anglais) de $w$.

Énoncé

Modèle:Théorème.

Une autre formulation

Un mot est morphiquement primitif s'il n'a pas d'autres points fixes que le morphisme identité. Par définition, un mot est morphiquement primitif si et seulement s'il n'appartient pas à l'ensemble FW. La conjecture de Billaud, par contraposition, s'énonce comme suit :

Discussion

Tester si un mot est morphiquement primitif peut se faire en temps linéaire. La conjecture de Billaud est une implication et non une caractérisation. Ainsi, alors qu'il existe des mots morphiquement non primitifs, tels que le mot $ababcdcd$ (point fixe du morphisme $a\mapsto ab$,$b,d\mapsto \epsilon$, $c\mapsto cd$), dont aucun des héritiers $ababcc$, $ababdd$, $aacdcd$ et $bbcdcd$ n'est morphiquement primitif, il existe également des mots tels que $abccbcca$, qui sont morphiquement imprimitifs, mais dont certains héritiers sont morphiquement primitifs (ici $abba$ et $acccca$).

Michel Billaud est, de 1984 à 2021, Maître de Conférences au Département Informatique de l'Institut Universitaire de Technologie de l'Université Bordeaux ; il est membre du Laboratoire Bordelais d'Informatique (LaBRI)

Bibliographie

• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article

• Modèle:Article